선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬

 정렬은 파이썬에서 라이브러리 함수가 존재하므로 간단하게 정리하고 넘어가겠다! 그래도 계수 정렬은 처음 보는 방법이었다.

 선택 정렬

 주관적인 생각으로 가장 원초적인 방법이다. 왼쪽부터 (맨 앞부터) 가장 작은 숫자를 찾아서 맨 앞으로 위치를 바꾼다. 

그다음 방금 바꾼(현재 가장 왼쪽에 있는) 원소 다음부터 가장 작은 숫자를 찾아서 두 번째로 위치를 바꾼다. 마지막까지 반복한다. 느리다.

삽입 정렬

 첫 번째 숫자는 정렬이 되어있다 생각하고 두 번째부터 진행한다. 첫 번째보다 작으면 왼쪽으로 크면 그대로 둔다. 그다음 세 번째 숫자를 자신의 왼쪽에 있는 숫자들과 비교하며 적절한 위치에 둔다. 무한 반복. 조금 두리뭉실한 것 같아 예시로 설명하면 

ex) 3,2,6,7,4,1 이 있다고 하자 두 번째인 2부터 시작한다 자신의 왼쪽인 3보다 작으므로 위치를 바꾼다. => 2,3,6,7,4,1

세 번째 숫자 6으로 비교한다. 자신의 왼쪽보다 크므로 그대로 둔다. 7도 마찬가지. 그다음 4를 왼쪽 숫자들과 비교한다. 적절한 위치는 어디? 3과 6 사이이다. 2,3,4,6,7,1가 됐다. 1도 마찬가지로 진행하면 1,2,3,4,6,7 완성. 그냥 차례대로 왼쪽과 비교하여 적절한 위치에 삽입한다. 느리다.

퀵 정렬

 이름대로 빠른 정렬이다. 기준점(피벗)을 설정하여 반복한다. 예시로 바로 설명하겠다. 5,6,1,3,2,4 첫 번째 숫자를 피벗으로 사용한다. 피벗을 제외하고 왼쪽에서부터(6)  피벗(5) 보다 큰 숫자를, 오른쪽에서부터(4) 피벗보다 작은 숫자를 한 칸씩 옮겨가며 찾는다. 왼쪽에서는 6, 오른쪽에서는 4가 선택된다. 둘의 위치를 바꾼다. 5,4,1,3,2,6 다시 반복한다. 이때 왼쪽(5보다 큰 수 6)과 오른쪽(5보다 작은 수 2)이 교차되었다. 이러면 작은 수(오른쪽 2)와 피벗(5)을 바꾼다. 2,4,1,3,5,6 이렇게 되면 피벗 5를 기준으로 피벗보다 작은 수(피벗 왼쪽), 큰 수(피벗 오른쪽)로 나누어진다. 이 나누어진 부분을 각각 나누어 다시 정렬한다. (왼쪽인 2,4,1,3을 2를 피벗으로 같은 동작 반복) 이를 파이썬을 활용해 간단하게 줄일 수 있다. 피벗을 기점으로 왼쪽은 작은 수, 오른쪽은 큰 수로 만든 다는 것을 이용한 것이다.

def quick_sort(array):
	#array가 길이가 1이면 끝!
	if len(array) <= 1:
    	return array
	
    #피벗은 첫번째 원소, tmp_array는 피벗을 제외한 비교할 원소
    pivot = array[0]
    tmp_array = array[1:]
    
    #피벗보다 작은건 왼쪽~ 큰 건 오른쪽~ 왼쪽,오른쪽에서 한 칸씩 이동할 필요없이 바로 저장!
    left = [x for x in tmp_array if x <= pivot]
    right = [x for x in tmp_array if x > pivot]
    
    #나눠진 부분 다시 정렬(재귀)해서 합치기~
    return quick_sort(left) + pivot + quick_sort(right)

 계수 정렬

 계수 정렬은 특정한 조건(크기가 제한되어 있거나 작을 경우 등)이 맞을 때 사용할 수 있는 매우 빠른 알고리즘이다.

 7,4,2,5,1,5,3,2,9이 있다고 하자. 그러면 크기가 10인 리스트(count라고 선언하겠다.)를 만들고 각 인덱스마다 값은 0으로 초기화한다. 그런 다음 정렬해야 하는 수들을 하나씩 읽어 만든 리스트의 수를 하나 씩 증가한다. 예를 들면 7을 읽고 count [7]의 값을 1로 증가시킨다. 4,2,5.. 모두 마찬가지이다. 그렇다면 count 리스트에는 인덱스의 수가 몇 개 있는지 저장된다. 그런 다음 인덱스 값을 원자 값만큼 출력하면 정렬이 된다! count [0] 0은 0개 있으므로 출력 X,  7,4,2,5,1,5,3,2,9에 1이 1개 있으므로 count [1] = 1이다. 인덱스인 1을 원자 값만큼 1번 출력,  2는 두 개 있으므로 count [2] = 2이므로 인덱스 2를 원자 값만큼 2번 출력! 따로 비교 연산을 진행하지 않고 정렬을 할 수 있다. 하지만 만약에 정렬해야 하는 값이 99999, 1이면 리스트를 0~99999까지 만들어야 한다. 그럼 2개의 인덱스 말고는 쓸데없는 생성이 된다. 그래서 특정한 조건에 맞을 경우 사용해야 한다고 한 것이다! (딕셔너리로 처리하면 되지 않을까?라는 생각을 한번 해본다.)

 

 라이브러리 함수 sorted(), . sort()

정렬을 위한 문제가 아니라면 그냥 라이브러리 함수를 쓰면 된다. 

 

계수 정렬은 처음 보는 아이디어였다. 유익하다 유익해