정렬 알고리즘

Tsi0511·2023년 4월 5일

알고리즘 공부

목록 보기

4/6

선택정렬

두 번째 값부터 시작해 그 앞(왼쪽)의 자료들과 비교하여 삽입위치를 지정 후
자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 방법

# 배열을 인자값으로 넘겨준다.
def selection_sort(a):
	
    # 배열길이-1 만큼 반복
    for i in range(len(a)-1):  

        min = i  # 최소값을 i로 초기화

        #0(1씩 증가)번지와 나머지 번지들을 비교하여 
        for j in range(i+1, len(a)):
            #배열에서 가장작은값의 번지를 변수 min에 담아준다.
            if a[j] < a[min]:
                min = j
        #최소값의 위치를 맨 앞으로 보내준다.
        a[i], a[min] = a[min], a[i]

배열이 어떤 형태든 동일한 연산을 하므로
다른 O(N^2)의 시간복잡도를 가지는 정렬방식보다 구리다.

시간복잡도: O(N^2)

삽입정렬

정렬 범위를 1칸씩 확장해나가면서 새롭게 정렬 범위에 들어온 값을
기존 값들과 비교하여 알맞은 자리에 배치하는 방법

def insertion_sort(a):

    #start(탐색 시작점) 
    for start in range(1, len(a)): 

        #점점 탐색범위를 1씩 늘려준다.
        for i in range(start, 0, -1):

            #바로 앞에 위치한 값이 i번지 값보다 크면 (2개씩 비교)
            if a[i - 1] > a[i]:
                a[i - 1], a[i] = a[i], a[i - 1] #스왑해준다.
            
            #잘 정렬이 되있다면 굳이 안건드리기.

선택/거품정렬은 반복문이 거듭될수록 탐색범위가 줄어들지만
삽입정렬은 늘어나는게 특징이다.

시간복잡도: O(N^2),

(완전히 정렬된 배열의 경우 O(N)의 시간복잡도를 가진다.)

퀵정렬

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할 후
분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여
전체가 정렬된 리스트가 되게 하는 방법

분할 정복 (Devide and Conquer) 기법과 재귀 알고리즘을 이용한 정렬 알고리즘

#빠른정렬
def quick_sort(a):

    #정렬할게 없는 1개 이하의 값을 가진 배열은
    if len(a) <= 1:
        return a #그대로 리턴
    
    #pivot값은 배열의 가운데에 해당하는 위치값으로 지정
    pivot = a[len(a) // 2]

    #pivot값보다 작은 값, 동일한 값, 큰 값을 담을 배열 선언
    small, center, big = [], [], []

    #비교 후 리스트 추가
    for i in a:
        if i < pivot:
            small.append(i)
        elif i > pivot:
            big.append(i)
        else:
            center.append(i)
            
	#작은 값과 큰 값을 담고있는 배열을 재귀호출 후 
    #결과를 크기 순으로 합치면 정렬된 배열을 얻을 수 있다.
    return quick_sort(small) + center + quick_sort(big)

매우 빠른 수행속도를 자랑한다.
프로그래밍 언어 차원에서 기본적으로 지원되는 내장 정렬 함수
대부분은 퀵 정렬을 기본으로 한다.

시간복잡도: O(nlog(n))

(pivot값 기준으로 분할했을 때 모든 값이 한 쪽으로 몰리는
최악의 경우엔 O(n^2)가 된다.)

계수정렬

가장 작은 데이터부터 가장 큰 데이터까지 담길 수 있는 배열 선언 후
데이터를 하나씩 확인하며 데이터 값과 동일한 번지값을 1씩 증가시키고
증가된 번지값들 중 0을 제외하고 인덱스를 인덱스 값만큼 출력하는 방법

def counting_sort(a):
	# a의 모든범위를 포함하는 배열 선언
	c=[0]*(max(a)+1)

	# 배열의 요소에 해당하는 번지 카운트해주기
	for i in a:
			c[i]+=1 

	#c에서 카운트 된만큼 해당숫자 출력 
	for i in range(len(c)): 
			for j in range(c[i]): 
					print(i, end=' ')