[이것이 코딩 테스트다] CH06. 정렬

선택 정렬

매번 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복 수행하여 오름차순으로 정렬하는 방법

# 선택 정렬 예시
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)): #i=0부터
    min_index = i
    for j in range(i+1, len(array)): #j=1부터 
        if array[min_index] > array[j]: 
            min_index = j #가장 작은 원소의 index를 min_index에 저장
    array[i], array[min_index] = array[min_index], array[i] #swap
    
print(array)

선택 정렬 예시 - 결과

시간복잡도 = O(N²), N + (N-1) + ... + 2 의 빅오표기법

 

삽입 정렬

데이터를 적절한 위치에 삽입하여 정렬하는 방법.

- 거의 정렬된 상태로 입력이 주어진 문제에서 유리.

# 삽입 정렬 예시
array = [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]  #왼쪽으로 한 칸씩 이동
        else:
            break #반복문 끝내기

print(array)

삽입 정렬 예시 -결과

시간복잡도 = O(N²), 반복문이 2번 중첩되어 사용됨.

※정렬이 이루어진 원소는 항상 오름차순을 유지하고 있음.※

퀵정렬