[Algorithm] 정렬 알고리즘( 선택, 삽입, 퀵, 계수)

Jifrozen·2021년 7월 19일

Algorithm

목록 보기

25/70

정렬 알고리즘

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말합니다.
-일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.
정렬 알고리즘을 통해 정렬하면 이진탐색이 가능해진다.

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

현재 존재하는 데이터중 가장 작은 값 0을 선택해 맨 앞 데이터와 바꿔줌
다음 1 데이터 선택해 처리되지 않은 데이터중 맨앞 데이터 5와 바꿔줌
.
.
반복
0 1 2 3 4 5 6 7 8 9
정렬 성공

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

# 선택정렬
for i in range(len(array)):
    min_index = i
    for j in range(i + 1, len(array)):
        if array[min_index] > array[j]:
            min_index = j
    array[i], array[min_index] = array[min_index], array[i]
print(array)

선택 정렬 시간복잡도

선택 정렬은 n 번만큼 사장 작은 수를 찾아서 맨 앞으로 보내야한다.
N+(N+1)+(N+2)...+2( 마지막 값은 자동으로 정렬 )
(N^+N-2)/2이다. 따라서 빅오 표기법으로는 O(n^)이다.

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입
선택정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 효울적이다.
앞에 있는 데이터가 정렬되어 있다고 가정하고 뒤에 데이터를 정렬해줌

맨 앞 7은 정렬되었다고 가정하고 두번째 5를 7과 비교해 작으면 왼쪽 크면 오른쪽에 위치 시킴
5 7 | 9 0 3 ...
9를 5 7 과 비교해 5 7 9 | 0 3 . . .
0 5 7 9 | 3 1 6 . . .
위에 반복시킨다.


#삽입 정렬
for i in range (1,len(array)): # j 현재 삽입하고자 하는 데이터
    for j in range (i,0,-1): # 인덱스 i부터 1까지 -1씩 감소하며 반복
        if array[j]<array[j-1]:  # 현재 삽입하고자 하는 데이터와 바로 왼쪽 데이터 비교해서 작으면
            array[j],array[j-1]=array[j-1],array[j] # 왼쪽 데이터와 바꿈
        else: # 크면
            break # 그대로

삽입 정렬 시간복잡도

삽입 정렬의 시간 복잡도는 O(N^)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.
삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 잇는 상태라면 매우 빠르게 동작한다.
최선의 경우 O(N)의 시간 복잡도를 가진다.
따라서 거의 정렬된 데이터를 정렬하고자할때 삽입 정렬을 이용하는것이 좋다.

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나이다.
-병학 정렬과 더불어 대부분의 프로그래밍 언어 정렬 라이브러리의 근간이 되는 알고리즘이다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준데이터(pivot)로 설정한다.

pivot데이터를 5로 정한다.
pivot 데이터를 기준으로 왼쪽부터 큰값7을 선택하고 오른쪽부터는 작은값4을 선택한다.
5 | 7 9 0 3 1 6 2 4 8
둘의 위치를 바꿔준다.
5 | 4 9 0 3 1 6 2 7 8
위의 단계를 반복한다.
5 | 4 9 0 3 1 6 2 7 8
5 | 4 2 0 3 1 6 9 7 8
위치가 엇갈리는 경우
5 4. 0 3 1 6 9 7 8
작은 데이터와 pivot 데이터의 위치를 변경한다.
1 4. 0 3 5 6 9 7 8
pivot 을 중심으로 왼쪽은 모두 작은값 오른쪽은 모두 큰 값
분할(Divide) 된다. partition

1 4 2 0 3 왼쪽 데이터 모음에서 위 과정을 반복한다.
6 9 7 오른쪽 데이터 모음에서 위 과정을 반복한다.

컴퓨터 과학에서 logN 은 보통 밑이 2인 로그라고 한다..!

# 퀵 정렬
def quick_sort(array, start,end):
    if start>=end:
        return
    pivot=start
    left=start+1
    right=end
    while(left<=right): # left가 right 보다 커진다면
        # 선형탐색 피봇보다 왼쪽에서 큰 값을 찾을때까지
        while(left<=end and array[left]<=array[pivot]):
            left+=1
        while(right>start and array[right]>=array[pivot]):
            right-=1
        if (left>right): # 엇갈렸다면 작은 데이터와 피봇 대체
            array[right],array[pivot]=array[pivot],array[right]
        else:
            array[left],array[pivot]=array[right],array[left]
    # 재귀적으로 왼쪽 오른쪽 각각 정렬 다시
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)


# 파이썬의 장점을 살린 퀵정렬
def quick_sort2(array):
    if len(array)<=1:
        return array
    pivot =array[0]
    tail=array[1:0] # 피봇을 제외한 리스트

    left_side=[x for x in tail if x<=pivot]
    right_side=[x for x in tail if x>pivot]

    return quick_sort2(left_side)+[pivot]+quick_sort2(right_side)

퀵정렬의 시간 복잡도

퀵 정렬은 평군의 경우 O(NlogN)의 시간 복잡도를 가진다.
하지만 최악의 경우 O(n^)의 시간 복잡도를 가집니다.
이미 정렬된 정렬으로 생각하면 0 1 2 3 4 5 6

계수 정렬

특정한 조건이 부합할 때만 사용할 수 있지만 매우 빠르게 동작하는 정렬 알고리즘이다.
계수 정렬은 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을때 사용 가능
데이터의 개수 N, 데이터(양수) 최댓값이 K일때 최악의 경우에도 수행시간 O(N+K) 보장

각 원수 개수를 다 구한 뒤 리스트의 첫번째 데이터부터 하나씩 그 값만큼 반복하여 인덱스를 출력
001122345567899

각 데이터 몇번씩 등장햇는지 세고 출력한다.

# 계수 정렬
count=[0]*(max(array)+1)

for i in range (len(array)):
    count[array[i]]+=1

for i in range (len(count)):
    for j in range (count[i]):
        print(i,end='')