정렬

1. 버블정렬
   시간복잡도는 O(n^2)
   "인접한" 두 원소를 비교하여 큰 원소를 뒤로 보내는 것으로 정렬하는 방법.
   
   순회를 마칠 때 마다 비교 대상이 하나씩 줄어들기 때문에, 전체 원소의 개수가 n개 라고 할 때, 총 n-1 번 순회하면 정렬이 끝남.

구현은 간단하지만, 비교 할 데이터수가 많을수록 비효율적이다.

참고할 블로그(링크텍스트)

백준 2750

N = int(input())

nums = []

for _ in range(N) : 
    nums.append(int(input()))

for i in range(len(nums)) : 
    for j in range(len(nums)) : 
        if nums[i] < nums[j] : 
            nums[i], nums[j] = nums[j], nums[i]
            
for n in nums : 
    print(n)

삽입정렬
작은 원소를 골라 앞쪽부터 정렬
삽입 정렬(揷入整列, insertion sort)은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.(위키)

앞에서부터 차례대로
이미 정렬된 배열과 비교
자신의 위치를 찾아 삽입

배열이 길어질수록 효율이 떨어진다. 다만, 구현이 간단하다는 장점이 있다.

선택 정렬이나 거품 정렬과 같은 같은 O(n2) 알고리즘에 비교하여 빠르다.

31	25	12	22	11		
처음 상태.
31	[25]	12	22	11		 	
두 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<25>	31	[12]	22	11		 	
세 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<12>	25	31	[22]	11		 	'
네 번째 원소를 부분 리스트에서 적절한 위치에 삽입한다.
12	<22>	25	31	[11]		 	
마지막 원소를 부분 리스트에서 적절한 위치에 삽입한다.
<11>	12	22	25	31		 	
종료.

예제

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

백준 2750

N = int(input())
nums = []

for _ in range(N) : 
    nums.append(int(input()))

# Insert Sort
for i in range(1, len(nums)) :
    while (i>0) & (nums[i] < nums[i-1]) :
        nums[i], nums[i-1] = nums[i-1], nums[i]
        
        i -= 1
        
for n in nums : 
    print(n)

선택정렬

선택 정렬(選擇整列, selection sort)은 제자리 정렬 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.

주어진 리스트 중에 최소값을 찾는다.
그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)).
맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
비교하는 것이 상수 시간에 이루어진다는 가정 아래, n개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다.

패스	    테이블	       최솟값
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8

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