6장 정렬 알고리즘 - 1

정렬이란?

값의 대소관계에 따라 데이터 집합을 일정한 순서로 바꾸어 늘어놓는 작업을 말한다.
작은 데이터를 앞쪽부터 늘어놓은 것을 오름차순 큰 데이터를 앞쪽부터 늘어놓은 것을 내림차순이라 한다.
정렬 알고리즘에서 교환, 선택, 삽입은 핵심 개념이다.

1. 버블 정렬

이웃한 원소를 비교하여 작은값을 앞으로 큰값을 뒤로 교환하는 정렬을 말한다.

코드 구현

arr = [6,4,3,7,1,9,8]  

for i in range(len(arr)):  
    for j in range(len(arr)-i-1,i,-1):  
        if arr[j-1] > arr[j]:  
            arr[j], arr[j-1] = arr[j-1], arr[j]

2. 세이커 정렬(버블 정렬 개선)

정렬이 거의 완료된 배열을 버블정렬하면 빠르게 완료하기가 어렵다.
가장 큰 원소가 맨 앞에 있을 경우 한칸씩 뒤로가기 때문이다.
그래서 개선한 방법이 세이커 정렬이다.
홀수 패스에서 가장 작은 원소는 맨 앞으로 이동하고 짝수 패스에서 가장 큰 원소를 맨 뒤로 보내 버블정렬의 단점을 보완했다.

코드 구현

arr = [9,1,2,3,4,5,6]  

left, right = 0, len(arr) - 1  
last = right  
while left < right:  
    for i in range(right, left, -1):  
        if arr[i - 1] > arr[i]:  
            arr[i], arr[i - 1] = arr[i - 1], arr[i]  
            last = i  
    left = last  

    for i in range(left, right):  
        if arr[i] > arr[i + 1]:  
            arr[i], arr[i + 1] = arr[i + 1], arr[i]  
            last = i  
    right = last

3. 단순 선택 정렬

가장 작은 원소를 선택해 알맞은 위치로 옮기는 작업을 반복해 정렬하는 알고리즘을 말한다.

코드 구현

arr = [6, 4, 8, 3, 1, 9, 7]  

for i in range(len(arr) -1):  
    min = i  
    for j in range(i + 1, len(arr)):  
        if arr[j] < arr[min]:  
            min = j  
    arr[i], arr[min] = arr[min], arr[i]

4. 단순 삽입 정렬

주목한 원소보다 더 앞쪽에서 알맞은 위치로 삽입하며 정렬하는 알고리즘이다.
단순 선택 정렬과 비슷하지만 가장 작은 원소를 선택하지 않는다는 점이 다르다.

코드 구현

arr = [6, 4, 8, 3, 1, 9, 7]  

for i in range(1, len(arr)):  
    j = i  
    tmp = arr[i]  
    while j > 0 and arr[j -1] > tmp:  
        arr[j] = arr[j -1]  
        j -= 1  
    arr[j] = tmp

참고) Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편