6-1. 정렬(선택정렬,삽입정렬,퀵정렬,계수정렬)

1. 선택정렬

 

선택정렬 코드

 

선택정렬 시간복잡도

삽입정렬

삽입 정렬 소스코드

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부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j-1]: #한 칸씩 왼쪽으로 이동
            array[j],array[j-1] = array[j-1],array[j]
        else: #앞쪽은 이미 정렬이 되어있기 때문에 자기보다 작은 데이터 만나면 그자리에서 멈춤
            break
print(array)

삽입정렬 시간 복잡도

퀵 정렬

소스코드

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

def quick_sort(array,start,end):
    if start >= end: #원소가 1개인 경우 종료
        return
    pivot = start #피벗은 첫 번째 원소
    left = start + 1
    right = end
    while(left <= right):
        #피벗보다 큰 데이터를 찾을 때까지 반복
        while(left <= end and array[left] <= array[pivot]):
            left+=1
        #피벗보다 작은 데이터를 찾을 때까지 반복
        while(right > start and array[right] >= array[pivot]):
            right -=1
        if(left > right): #엇갈렸다면 작은 데이터와 피벗을 교체
            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)

소스코드2

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

def quick_sort(array):
    #리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    pivot = array[0] #피벗은 첫 번째 원소
    tail = array[1:] #피벗을 제외한 리스트

    left_side =[x for x in tail if x <= pivot] #분할된 왼쪽 부분
    right_side = [x for x in tail if x>pivot] #분할된 오른쪽 부분

    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행하고 전체 리스트 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

계수 정렬

소스코드

#모든 원소의 값이 0보다 크거나 같다고 가정
array=[7,4,9,0,3,1,6,2,9,1,4,8,0,2,2]

#모든 범위를 포함하는 리스트 선언(모든 값은 0으로 초기화)
count = [0] * (max(array) +1 )

for i in range(len(array)):
    count[array[i]] += 1 #각 데이터에 해당하는 인덱스 값 증가

for i in range(len(count)): #리스트에 기록된 정렬 정보 확인
    for j in range(count[i]):
        print(i,end=" ") #띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

계수 정렬의 복잡도

 

4개의 정렬 알고리즘 비교

 

선택정렬과 기본 정렬 라이브러리 수행 시간 비교