[파이썬] '정렬' 개념 및 예제

이것이 취업을 위한 코딩 테스트다 with 파이썬 강의 참고

 

1. 선택 정렬 O(N^2)

현재 범위 내에서 가장 작은 데이터 선택해서 맨 앞의 데이터와 변경.

(범위 : 앞으로 데이터를 보내면서 남은 만큼)

->제일 작은거 맨앞으로 보내고, 남은 것 중 작은거 앞에서 두번째로 보내고, 남은 것 중 작은거 앞에서 3번째로 ..

* 마지막 경우는 처리 안해도 됨.

 

array= [7,5,9,0,3,1,6,2,4,8]

for i in range(len(array)):
	min=i #가장 작은 원소 인덱스
    for j in rnage(i+1 , len(array)):
    	if array[min] > array[j]:
        	min=j
    array[i],array[min] = array[min], array[i] # swap
    # 파이썬은 위와 같이 swap을 쉽게 할수 있다.
    
    print(array) # [0,1,2,3,4,5,6,7,8,9]

 

2. 삽입 정렬 O(N^2) , 이미 정렬한 상태: O(N)

데이터를 순차적으로 하나씩 골라 앞의 데이터와 비교해서 적절한 위치 (앞,뒤)에 삽입

-> 앞에 애들이랑(=왼쪽으로) 한칸씩 비교하면서 갈수있는 제일 왼쪽까지 감.

(선택정렬 보다 어려움, 효율적)

array= [7,5,9,0,3,1,6,2,4,8]

for i in range(1, len(array)):
	for j in range(i, 0, -1): # i부터 0 전까지 1씩 감소 ( = i부터 1까지)
    # j: 삽입하고자 하는 위치
		if array[j] < array[j-1]: #한 칸씩 왼쪽으로 (앞이 더 컸다면)
			array[j] , array[j-1] = array[j-1], array[j]
		else: #자기보다 작은 데이터 만나면 그 위치에서 멈춤
			break
print(array) #[0,1,2,3,4,5,6,7,8,9]

 

퀵 & 병합 : 가장 많이 사용

 

3. 퀵 정렬 O(NlogN) ,이미 정렬한 상태: O(N^2) 최악 - 첫번째 원소 pivot일때

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꿔줌

기본 : 첫번째 데이터가 기준 데이터 (Pivot)

 

1. 첫번째 데이터를 pivot으로 둠

2. 두번째 데이터( →) 부터 시작해서 pivot보다 큰 것과, 마지막( ← ) 부터 시작해서 pivot보다 작은것을 서로 바꿔줌.

3. 계속 바꿔줌

4.  큰 것과 작은것의 위치가 엇갈렸을때 !   =>   작은것과 pivot의 위치를 변경.

5. (pivot보다 작음) (pivot) (pivot보다 큼) 과 같은 형태가 되고, pivot을 제외한 두 덩어리에서 각각 퀵정렬 수행 (재귀)

 

표준 라이브러리 사용시 항상 N(logN) 보장 

 

array=[5,7,9,0,3,1,6,2,4,8]

def quick_sort(array, start, end):
	if start>=end: #원소 1이면 종료
    	return
    pivot=start #picot=첫번째 원소
    left=start+1
    right=end
    while(left<=right): 
    	while(left <= end and array[left] <= array[pivot]):
    		left+=1 # 왼쪽에선 pivot 보다 큰거 찾을때 까지 반복
    	while(right > start and array[right] >= array[pivot]):
    		right=-1 # 오른쪽에선 pivot보다 작은거 찾을때 까지 반복
    	if(left>right): #엇갈리면 pivot이랑 작은거 교체
    		array[right], array[pivot] = array[pivot], array[right]
    	else: #안 엇갈렸으면 큰거랑 작은거 교체
    		array[left],array[right] = array[right],array[left]
    #분할 이후 왼쪽, 오른쪽에서 각각 퀵소트 진행
    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)

quick_sort(array,0,len(array)-1)
print(array) # [0,1,2,3,4,5,6,7,8,9]
    

+) 파이썬 장점 살린 방식 (간결한 퀵소트)

def quick_sort(array):
	if len(array) <=1:
		return array
	pivot=array[0]
	tail=array[1:] #pivot 제외한 리스트
	
	left=[x for x in tail if x<=pivot]
	right=[x for x in tail if x>picot]
	
	return quick_sort(left)+[pivot]+quick_sort(right)

print(quick_sort(array))

 

4. 계수정렬

추후 업데이트 예정