코딩테스트 - 정렬

코딩테스트를 준비하다보니 정렬을 정리하면 좋을 것 같다는 생각을 했다.

1. 정렬
   정렬이란, 데이터를 특정 기준에 맞춰서 나열하는 것을 말한다. 사실 코딩테스트 문제에서는 정렬되어 있는 경우가 많다. 하지만, 그렇지 않은 경우도 있고 기존에 정렬되어 있는 데이터를 새로운 기준을 가지고 정렬하는 경우도 있다. 정렬에는 다양한 알고리즘이 있다. 다양한 알고리즘이 있는만큼 각 방법에는 장단점이 존재한다. 그리고 자연스럽게도 시간차이도 존재한다. 따라서 문제를 풀다가 시간초과가 발생하게 된다면 다른 알고리즘을 사용해야 한다. 사실 정렬 알고리즘은 1학년 때 배운 것 같기는 하다. 그런데 시간이 너무 지나서 다 까먹었다.... 정렬 알고리즘에는 종류가 많은 것으로 알고있다. 하지만 나는 그 중에서 대표적인 것들만 몇개 정리하려 한다. 추후에 추가가 될지, 아니면 다른 글로 포스팅할지는 모르겠다.

2. 선택 정렬
   선택된 값과 나머지 데이터를 비교하여 알맞은 자리를 찾는 알고리즘이다. 현재 위치에 저장할 값의 크기가 작은지 큰지에 따라서 최소 선택 정렬, 최대 선택 정렬로 구분한다.

• 정렬되지 않은 데이터의 인덱스의 맨 앞부터, 이를 포함한 이후에 데이터의 값 중에서 가장 작은 값(가장 큰 값)을 찾는다.
• 가장 작은 값(가장 큰 값)을 찾으면, 그 값을 현재 인덱스의 값과 바꾼다.
• 다음 인덱스로 넘어가 위의 과정을 반복한다.

3. 삽입 정렬
   데이터를 순회하면서 정렬이 필요한 데이터만을 뽑아내어 알맞은 위치의 삽입하는 알고리즘이다.
   기존의 데이터를 정렬된 부분과 정렬이 필요한 부분으로 구분해야 한다. 나는 생각하기 쉽게 데이터의 맨 처음은 정렬된 부분, 그 다음부터는 정렬이 필요한 부분이라고 생각하고 진행하겠다.

• 정렬이 필요한 데이터의 값과 정렬된 데이터의 값들을 비교
• 정렬된 데이터의 현재 값과 비교해서 정렬이 필요한 데이터의 값이 작으면(크면) 데이터 삽입
• 정렬이 필요한 데이터의 다음 인덱스로 넘어가 반복

4. 버블 정렬
   매번 연속된 두개의 인덱스를 비교하여 데이터의 위치를 정해서 정렬하는 알고리즘이다.

• 인덱스의 맨 앞에서 시작, 두 인덱스를 비교해서 큰 값을 뒤로 이동
• 인덱스를 한 바퀴 돌게 되면, 기존의 데이터 중에서 가장 큰 값이 맨 마지막으로 위치
• 모든 데이터가 정렬될 때까지 반복

5. 퀵 정렬
   분할 정복 알고리즘을 사용한 정렬 알고리즘이다. pivot point라고 하는 기준이 되는 값을 하나 설정하게 된다. 이 값을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮기는 방식이다.

• 정렬되지 않은 데이터 값 중에서 pivot point 설정
• pivot point를 기준으로 왼쪽에는 작은 데이터, 오른쪽에는 큰 데이터들을 위치
• 왼쪽에 데이터 집합에서 다시 수행하며 데이터 집합의 크기가 1이 될 때 까지 반복

6. Code

import random

random_data = random.sample(range(1,11), 10)
print("정렬할 데이터: ", random_data)


def select_sort(data):
    for index in range(len(data)):
        if index == len(data) - 1:
            break
        
        min_index = index
        
        for right in range(index+1, len(data)):
            if data[right] < data[min_index]:
                min_index = right

        data[index], data[min_index] = data[min_index], data[index]

    return data


def insert_sort(data):
    for index in range(len(data)):
        if index == 0:
            continue

        insert_index = 0
        left_data = data[:index]

        for left in range(len(left_data)):
            if data[index] > data[:index][left]:
                insert_index = left + 1

        left_data.insert(insert_index, data[index])
        data = left_data + data[index+1:]

    return data


def bubble_sort(data):
    for index in range(len(data)):
        for right in range(index+1, len(data)):
            if data[index] > data[right]:
                data[index], data[right] = data[right], data[index]

    return data


def quick_sort(data):
    if len(data) < 2:
        return data

    pivot_index = random.randint(0, len(data)-1)
    small_data, same_data, big_data = [], [], []

    for index in range(len(data)):
        if data[index] > data[pivot_index]:
            big_data.append(data[index])
        elif data[index] < data[pivot_index]:
            small_data.append(data[index])
        else:
            same_data.append(data[index])

    return quick_sort(small_data) + same_data + quick_sort(big_data)


print("선택 정렬: ", select_sort(random_data))
print("삽입 정렬: ", insert_sort(random_data))
print("버블 정렬: ", bubble_sort(random_data))
print("퀵 정렬: ", quick_sort(random_data))

출력

정렬할 데이터:  [1, 10, 3, 6, 9, 7, 2, 4, 5, 8]
선택 정렬:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
삽입 정렬:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
버블 정렬:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
퀵 정렬:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

음....각각 하기 귀찮아서 한꺼번에 했다. 각각 정렬이 잘 되는 것을 확일 할 수 있다. 대신에 각각의 알고리즘마다 안정성도 다르고 시간복잡도도 다르다. 따라서 정렬 알고리즘을 사용할 때는 안정성과 시간복잡도를 고려해서 사용해야 한다.