기준에 따라 데이터를 정렬

Sorting이란 , 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다.
정렬 알고리즘으로 데이터를 정렬하면 다음 장에서 배울 이진 탐색(Binary Search)이 가능해진다.

정렬 알고리즘은 이진 탐색의 전처리 과정.
-가장 많이 사용하는 <선택정렬, 삽입정렬,퀵정렬, 계수정렬>

1. 선택정렬

컴퓨터가 데이터를 정렬할 때.
데이터가 무작위로 여러 개 있을 때, 이 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정을 반복하면?
= 이 방법은 가장 원시적인 방법으로 매번 '가장 작은 것을 선택'한다는 의미에서 선택 정렬(Selection Sort)알고리즘이라고 한다.
가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어진다.

정렬 알고리즘에서는 흔히 데이터의 개수 N이라고 표현.
다음 예제에서는 N=10인 경우를 가정
회색 카드= '현재 정렬되지 않은 데이터 중에서 가장 작은 데이터'를 의미
하늘색 카드 = '이미 정렬된 데이터'의미

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-1번 만큼 가장 작은 수를 찾아서 맨 앞으로.
구현 방식에 따라서 사소한 오차는 있지만 연산 횟수는
n+ (n-1) +(n-2)+ ...+2 로 볼 수 있다.
빅오 표기법으로 간단히 O(N*2)이라고 표현할 수 있다.
직관적으로 이해하자면, 소스코드 상으로 간단한 형태의 2중 반복문이 사용되었기 때문이다.
선택정렬을 이용하는 경우 데이터의 개수가 10,000개 이상이면 정렬 속도가 급격히 느려지는 것을 확인할 수 있다.
또한 파이썬에 내장된 기본 정렬 라이브러리는 내부적으로 c언어 기반이며, 다양한 최적화 테크닉이 포함되어 더욱 빠르게 동작한다.