Kim Jisong

I am an amazing person.

Sort

Introduction

정렬의 종류

python list 내장 함수

sort

시간복잡도: O(nlogn)

res = ['5', '7', '4', '6', '8']
res.sort()
# ['4', '5', '6', '7', '8']

res = ['5', '7', '4', '6', '8']
res.sort(reverse=True)
# ['8', '7', '6', '5', '4']
import sys
input = sys.stdin.readline

N = int(input())
res = []
for _ in range(N):
    res.append(int(input()))

res.sort()

for o in output:
    print(o)

sorted

버블 정렬

오른쪽부터 왼쪽 방향으로 인접한 두 개의 숫자를 비교해서 교환하는 작업을 반복하는 정렬 알고리즘이다.

시간복잡도

  • Best: O(n²)
  • Avg: O(n²)
  • Worst: O(n²)

아래는 오름차순으로 정렬되도록하는 버블정렬을 파이썬으로 구현한 내용이다.

import sys
input = sys.stdin.readline

N = int(input())
res = []
for _ in range(N):
    res.append(int(input()))

def bubble_sort(lists) -> list:
  n = len(lists)
  result = lists
  for i in range(0, n):
    for j in range(n-1, i, -1):
      if result[j-1] > result[j]:
        result[j-1], result[j] = result[j], result[j-1]
  return result

output = bubble_sort(res)

for o in output:
    print(o)

선택 정렬

정렬되지 않은 숫자 배열 중 최소값을 선택해 왼쪽 끝에 추가하는 정렬 알고리즘이다. 수열 중에서 최소값을 찾을 때는 선형 탐색을 사용한다.

시간복잡도

  • Best: O(n²)
  • Avg: O(n²)
  • Worst: O(n²)
import sys
input = sys.stdin.readline

N = int(input())
res = []
for _ in range(N):
    res.append(int(input()))

def selection_sort(lists) -> list:
    n = len(lists)
    result = lists
    for i in range(0, n-1):
        min_index = i
        for j in range(i+1, n):
            if result[j] > result[min_index]:
                min_index = j
        if (min_index != i):
            result[i], result[min_index] = result[min_index], result[i]
    return result

output = selection_sort(res)

for o in output:
    print(o)

삽입 정렬

삽입 정렬은 수열의 왼쪽부터 순서대로 정렬하는 방식이다. 정렬되지 않은 우측 숫자와 정렬된 숫자 배열을 차례대로 비교하여 삽입하는 정렬 알고리즘이다.

시간복잡도

  • Best: O(n)
  • Avg: O(n²)
  • Worst: O(n²)
import sys
input = sys.stdin.readline

N = int(input())
res = []
for _ in range(N):
    res.append(int(input()))

def selection_sort(lists) -> list:
    n = len(lists)
    result = lists
    for i in range(0, result):
        selected = result[i]
        j = i -1
        while (j >= 0 and result[j] > selected):
            result[j+1] = result[j]
            j = j -1
        result[j+1] = selected
    return result

output = selection_sort(res)

for o in output:
    print(o)

병합 정렬

힙 정렬

카운팅 정렬

안정 정렬

Example

https://www.acmicpc.net/step/9

수 정렬하기

import sys
input = sys.stdin.readline

N = int(input())
res = []
for _ in range(N):
    res.append(int(input()))

res.sort()

for o in output:
    print(o)

수 정렬하기 2

수 정렬하기 3

import sys
input = sys.stdin.readline

N = int(input())

numbers = [0]*(10001)
for _ in range(N):
    num = int(input())
    numbers[num] += 1

for i in range(10001):
    if numbers[i] != 0:
        for _ in range(numbers[i]):
            print(i)

커트라인

https://www.acmicpc.net/problem/25305

import sys
input = sys.stdin.readline

N, k = map(int,input().split())
scores = list(map(int,input().split()))

scores.sort()
print(scores[N-k])

통계학

소트인사이드

https://www.acmicpc.net/problem/1427

import sys
input = sys.stdin.readline

string = input()

lists = []
for s in string:
    lists.append(s)

result = sorted(lists, reverse=True)
for r in result:
    print(r,end='')

좌표 정렬하기

https://www.acmicpc.net/problem/11650

import sys
input = sys.stdin.readline

N = int(input())

lists = []
for _ in range(N):
    x, y = map(int,input().split())
    lists.append((x,y))

result = sorted(lists, key=lambda x:(x[0], x[1]))
for r in result:
    print("{0} {1}".format(r[0],r[1]))

좌표 정렬하기 2

https://www.acmicpc.net/problem/11651

import sys
input = sys.stdin.readline

N = int(input())

lists = []
for _ in range(N):
    x, y = map(int,input().split())
    lists.append((x,y))

result = sorted(lists, key=lambda x:(x[1],x[0]))
for r in result:
    print("{0} {1}".format(r[0],r[1]))

단어 정렬

주의

sys.stdin.readline()은 개행문자까지 입력에 받는다. 따라서, 스트링을 입력받을 때는 .rstrip()을 사용하는게 좋다

import sys
input = sys.stdin.readline

N = int(input())

lists = []
for _ in range(N):
    string = input().rstrip("\n")
    if string not in lists:
        lists.append(string)

result = sorted(lists, key=lambda x:(len(x),x))

for r in result:
    print(r)
import sys

N = int(input())

lists = []
for _ in range(N):
    string = input()
    if string not in lists:
        lists.append(string)

result = sorted(lists, key=lambda x:(len(x),x))

for r in result:
    print(r)

나이순 정렬

좌표 압축

import sys
input = sys.stdin.readline

N = int(input())

number_list = list(map(int,input().split()))
number = list(set(number_list))
number.sort()

number_dict = {}
for i in range(len(number)):
    number_dict[number[i]] = i
for n in number_list:
    print(number_dict[n], end=" ")

2022

Stack

1 minute read

Introduction

Stack

less than 1 minute read

Introduction

Download-only-one-directory

less than 1 minute read

Git 명령어를 사용한 하위 디렉토리 다운로드 Clone 할 로컬 저장소 생성

Sort

3 minute read

Introduction

Tree

less than 1 minute read

Introduction

Mutex library on C++

less than 1 minute read

#include <iostream> #include <thread> #include <chrono> #include <mutex> #include <atomic> #include <string.h>

TODO

less than 1 minute read

how to costom github blog using jekyll

Welcome to Jekyll!

less than 1 minute read

You’ll find this post in your _posts directory. Go ahead and edit it and re-build the site to see your changes. You can rebuild the site in many different wa...

Back to top ↑