정렬

출처 : 위키백과

선택 정렬

#1. 주어진 리스트 중에 최소값을 찾는다.
#2. 그 값을 맨 앞에 위치한 값과 교체한다.
#3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다

def selectionSort(x):
	length = len(x)
	for i in range(length-1):
	    indexMin = i
		for j in range(i+1, length):
			if x[indexMin] > x[j]:
				indexMin = j
		x[i], x[indexMin] = x[indexMin], x[i]
	return x

삽입 정렬

#자료 배열의 모든 요소를 앞에서부터 차례대로 
#이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성

def insert_sort(x):
	for i in range(1, len(x)):
		j = i - 1
		key = x[i]
		while x[j] > key and j >= 0:
			x[j+1] = x[j]
			j = j - 1
		x[j+1] = key
	return x

버블 정렬

#두 인접한 원소를 검사하여 정렬하는 방법

def bubbleSort(x):
	length = len(x)-1
	for i in range(length):
		for j in range(length-i):
			if x[j] > x[j+1]:
				x[j], x[j+1] = x[j+1], x[j]
	return x

합병 정렬

정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. 
(한 원소만 든 리스트는 정렬된 것과 같으므로)

부분리스트가 하나만 남을 때까지 반복해서 병합하며 정렬된 부분리스트를 생성한다. 
마지막 남은 부분리스트가 정렬된 리스트이다.

퀵 정렬

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

리스트 가운데서 하나의 원소를 고른다. 
이렇게 고른 원소를 피벗이라고 한다.

피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 
피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 
이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 

분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.

분할된 두 개의 작은 리스트에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 
재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.
재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 
이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

def quicksort(x):
    if len(x) <= 1:
        return x

    pivot = x[len(x) // 2]
    less = []
    more = []
    equal = []
    for a in x:
        if a < pivot:
            less.append(a)
        elif a > pivot:
            more.append(a)
        else:
            equal.append(a)

    return quicksort(less) + equal + quicksort(more)

문제

어떻게 해야할까

퀵 정렬, 버블 정렬 등등의 알고리즘이 필요할까 하다가 일단 sort로만 사용해보자 했는데 통과가 되어버렸다. 여태껏 풀었던 프로그래머스 문제중에 제일 난도가 낮은 문제인 것같다.

최종코드