0.정렬(Sort : bubble/insertion/merge/quick/selection feat.PYTHON)

1.bubble_sort

 

2중 for문으로 두원소를 비교해 가며 swap하여 정렬하는 알고리즘으로

이미 큰값으로 정렬이 끝난 index에 대해서는 연산을 하지 않습니다.

단순 2중 for문 이므로 time complexity : O(n^2)

 

def sort(array):
    for i in range(len(array)):
        for j in range(len(array)-i-1):
            if array[j+1] < array[j]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

-이미 실행한 루프는 돌지않게 하여 약간의 성능향상

 

 

2.insertion_sort

 

insertion sort는 비교연산을 적게하고 값 교환을 많이합니다.

입력 데이터 만큼 for문과 값을 옮기는 만큼 while문을 돌며 연산 하므로

정렬이 되어 있을수록 좋은 성능을 나타냅니다.

time complexity : O(n^2)

def sort(array):
    for i in range(len(array)-1):
        temp = array[i+1]                 # 속도향상을 위한 배열값 저장
        j = i
        while array[j] > temp and j >= 0:
            array[j+1] = array[j]         # 앞에 큰값을 뒤로 이동 - 한번이상
            j -= 1
        array[j+1] = temp                 # 뒤에 작은값을 앞으로 이동 - 한번
    return array

 

 

3.merge_sort

 

merge_sort는 길이 n이 1이 될 때까지 2로 나누어주는 BST와 마찬가지로 divide하여

merge하므로 BST와 같은원리로 (logn)만큼 divide 해주고 

merge하면서 값을 비교하여 정렬 하므로 최대 n번 정도의 복잡도로 동작하므로 

안좋아도 nlogn의 성능을 갖게 됩니다.

 

quick_sort pivot값 잘 골랐을 때와 같은 성능을 나타내고

임시로 저장할 공간을 못쓸 때는 quick_sort를 사용합니다.

time complexity : O(nlogn)

import sys
from sys import stdin
sys.setrecursionlimit(1500)

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    pivot = len(arr)//2
    left = merge_sort(arr[:pivot])
    right = merge_sort(arr[pivot:])
    return merge(left, right)


def merge(left, right):
    l_idx, r_idx, temp = 0, 0, []

    while l_idx < len(left) and r_idx < len(right):
        if left[l_idx] <= right[r_idx]:
            temp.append(left[l_idx])
            l_idx += 1

        else:
            temp.append(right[r_idx])
            r_idx += 1

    temp += left[l_idx:]
    temp += right[r_idx:]

    return temp


def sort(arr):
    return merge_sort(arr)

 

 

4.quick_sort

 

quick_sort는 pivot값을 얼마나 잘 고르냐에 따라 성능이 좌우됩니다. (partition)

pivot값보다 작은값과 큰값으로 왼쪽 오른쪽 배열 계속 나눔 (나눌때마다 pivot다시잡음)

partition이 왼쪽 오른쪽 하나씩 남을때 비교 정렬하면서 반환

최악의 경우 pivot이 partition을 너무 많이 나누면 n^2의 복잡도를 가지고

보통 nlogn의 복잡도를 가지는데 그 이유는 BST처럼 나누어 검색 결과가 줄어들기 때문 입니다.

time complexity : O(nlogn)

 

성능개선

pivot 랜덤값 or 중위값 -> 최악의 경우를 회피

insertion -> 성능개선(원소 개수가 적은 경우)

import sys
from sys import stdin
sys.setrecursionlimit(1500)

def quick_sort(arr):
    left, right, pivot = [], [], []
    if len(arr) <= 1:
        return arr

    for x in arr:
        if x < arr[len(arr)//2]:
            left.append(x)
        elif x > arr[len(arr)//2]:
            right.append(x)
        else:
            pivot.append(x)
        
    return quick_sort(left) + pivot + quick_sort(right)
    

def sort(arr):
    return quick_sort(arr)

arr = []
N = int(stdin.readline())
for x in range(N):
    arr.append(int(stdin.readline()))

for y in sort(arr):
    print(y)

 

 

5.selection_sort

 

selection sort는 비교연산을 많이하고 값 교환을 적게합니다.

가장 작은 수를 찾아 가장 앞에 두고

남은 수 중 가장 작은 수를 찾아 그 다음에 두는 방식으로 반복

time complexity : O(n^2) - worst, average, best경우 모두

def sort(array):
    for i in range(len(array)):
        min_value = array[i]
        min_index = i
        for j in range(i+1,len(array)):
            if min_value > array[j]: # 가장작은 최소값을 남은 배열에서 탐색
                min_value = array[j]
                min_index = j
        array[i], array[min_index] = array[min_index], array[i]   
    return array