기본적인 정렬 4가지

• 선택정렬 (Selection Sort)
• 삽입정렬 (Insertion Sort)
• 버블정렬 (Bubble Sort)
• 퀵정렬 (Quick Sort)

01. 선택정렬

: 해당 사이클의 데이터 중 최소값을 뽑아 맨 앞과 자리를 바꾸는 것

과정
1) array의 맨 앞 데이터를 minIdx로 지정
2) 그 뒤의 데이터들과 비교해가며 더 작은 값으로 minIdx 갱신
3) minIdx와 맨 앞 자리 바꿈

코드

def selectionSort(ary):
    n = len(ary)
    for i in range(0,n-1): 			# 맨 앞으로 초기화될 데이터들만큼 (cycle)
    	minIdx = i				# 맨 앞 데이터 minIdx로 초기화
        for k in range(i+1, n):	# 맨 앞의 다음 데이터부터 맨 끝 데이터(n-1)까지
        	if ary(minIdx) > ary(k):	# 최소값보다 더 작다면
            	minIdx = k			# 최소값 인덱스 갱신
     	tmp = ary[i]				# 자리바꿈
        ary[i] = ary[minIdx]
        ary[minIdx] = tmp
        
        return ary

성능

: O(n^2)
구려

02. 삽입정렬

: 들어올 데이터를 어디에 삽입할 지 지 앞의 데이터들과 비교해서 삽입하는 것

과정
1) 맨 앞 데이터는 맨 앞에 일단 내비둠
2) 그 다음에 데이터가 들어오면 그 앞에 애들과 뒤에서부터 비교
3) 비교 대상이 자기보다 크면 자리 바꿈

코드

def insertionSort(ary):
    n = len(ary)
    for end in range(1, n): 					# 들어올 애 기준 (1번~n-1번)
    	for cur in range(end, 0, -1): 				# 뒤에서부터 맨 앞에까지 비교
        	if ( ary[cur-1] > ary[cur] ):			# 앞에 있는 애가 나보다 크면
            	ary[cur-1], ary[cur] = ary[cur], ary[cur-1]	# 자리 바꿈
    return ary

성능

: O(n^2)
-> 선택정렬과 똑같이 구리지만, 이미 어느정도 정렬되어 있는 배열에 대해서는 훨 빠름.
최선의 시간복잡도 : O(N)

03. 버블정렬

: 앞에서부터 둘씩 비교해 자리바꿔가며 맨 뒤에 젤 큰 값이 오게하는 것 반복
: 고급정렬임^^

과정
1) 앞부터 앞뒤로 둘이 비교해가다보면 맨 뒤에 젤 큰 값이 옴
2) 젤 큰 값 빼고 반복쓰~

코드

def bubbleSort(ary):
    n = len(ary)
    for end in range(n-1, 0, -1):		# 마지막 데이터부터 역순으로 cycle에서 제껴짐
    	changeYN = False			# 자리 안 바꿔도 되면 break하기 위한 flag
    	for cur in range(0, end):		# 앞에서부터 마지막까지 둘씩 비교
        	if ( ary[cur] > ary[cur+1] ):	# 나보다 뒤가 더 작으면
            	ary[cur], ary[cur+1] = ary[cur+1], ary[cur]
                changeYN = True
        if not changeYN:			# changeYN이 False면 break
        	break
    return ary

성능

: O(n^2)
-> 여전하지만 많이 정렬되어있다면 성능이 엄청 좋아짐.

04. 퀵정렬

: pivot을 기준으로 작은 파트, 큰 파트 나누는 함수 재귀로 반복.

• 재귀호출 (반갈)
  - 종료조건: if start >= end: return
• 4가지 중 가장 빠르니까 중요함

과정
*) 재귀함수에서는 항상 종료조건이 있어야 함
1) pivot을 low, high의 중간값으로 설정

2) low가 high보다 작거나 같을 동안 3~5 반복
3) low에 해당하는 값이 pivot보다 작을 동안 low+1
4) high에 해당하는 값이 pivot보다 클 동안 high-1
5) low가 high보다 작거나 같으면 둘이 자리바꿈

6) mid = low
7) 작은쪽 큰쪽 재귀

코드

def qSort(arr,start,end):
    if end <= start:	# 재귀 종료조건
    	return
    
    low = start		# 변수 정의
    high = end
    
    pivot = arr[(low + high) // 2]	# pivot은 쟤네 중간값
    
    while low <= high:
    	while arr[low] < pivot:
        	low += 1
        while arr[high] > pivot:
        	high -= 1
        
        if low <= high:
        	arr[low], arr[high] = arr[high], arr[low]
                low, high = low+1, high-1
            
    mid = low
    
    qSort(ary, start, mid-1)
    qSort(ary, mid, end)
    
def quickSort(ary):
    qSort(ary, 0, len(ary)-1)

성능

: O(nlogn)
-> 가장 성능이 좋음.