정렬 : 오름차순 vs 내림차순

오름차순 기준으로 정리

선택정렬(O(n^2)) : 가장 작은 원소를 찾고 자리 교환

→ 어떤 경우에서나 시간이 같음 because 2중 for문이기 때문

from sys import stdin as s

n = int(s.readline())
number=[int(s.readline()) for i in range(n)]

for i in range(n):
    min_index = i
    for j in range(i+1,n): # 가장 작은 수의 인덱스 찾기(i+1부터가 핵심)
        if number[min_index] > number[j]:
            min_index = j
    number[i],number[min_index] = number[min_index],number[i] # 스왑

for i in number:
    print(i)

버블정렬(O(n^2)) : 거품처럼 올라오는 정렬

→ 어떤 경우에서나 시간이 같음 because 2중 for문이기 때문

from sys import stdin as s

n = int(s.readline())
number=[int(s.readline()) for i in range(n)]

for i in range(n::):
	for j in range(n):
		if number[j] < number[j+1]:
			number[j],number[j+1] = number[j+1],number[j]

삽입정렬(최선 : O(n), 최악 : O(n^2)) : 다른 원소의 앞과 뒤를 비교하여 충족하면 원소 삽입

→모든 원소가 내림차순일 때 최악의 경우 because 바뀔게 있을때만 while문이 돌기 때문

from sys import stdin as s

n = int(s.readline())
number=[int(s.readline()) for i in range(n)]

for i in range(n):
    j = i
    tmp = number[j] # 옮길 값 미리 빼둠
    while j > 0 and number[j-1]>tmp: # 리스트의 삽입계산
        number[j]= number[j-1]
        j -=1
    number[j]=tmp

for i in number:
    print(i)

퀵 정렬(평균 : O(nlogn), 최악 : O(n^2)) :

→피벗이 최대값일 때 최악의 경우 because 바뀔게 있을때만 while문이 돌기 때문 →알고리즘 문제에서는 n^2이라고 생각해야함

1단계 : 제일 좌측값을 피벗값으로 지정

2단계 : 피벗값을 제외하고 왼쪽에서는 피벗값보다 큰 값, 오른쪽에서는 피벗값보다 작은 값을 바꾸는 것을 반복

3단계 : 엇갈리는 경우, 작은 값을 피벗값과 바꿈

4단계 : 피벗값을 중심으로 좌우를 분할

5단계 : 정렬 될때까지 반복