[이코테] 정렬

선택 정렬

처리되지 않은 데이터 중 가장 작은 데이터를 선택 해 맨 앞에 있는 데이터와 바꾼다.

• 선택 정렬의 시간 복잡도

• N-1번 만큼 가장 작은 수를 찾아서 맨 앞으로 보낸다.
• 구현 방식에 따라서 사소한 오차는 있을 수 있지만,
  전체 연산 횟수는 다음과 같다.
  $N + (N - 1) + ( N - 2) + ... + 2$
  ⇒ $(N² + N - 2) / 2$ 등차수열
  ⇒ $O(N²)$ 차수 높은 항만 고려

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)

삽입 정렬

첫 번째 데이터는 그 자체로 정렬되어 있다고 판단하고, 두 번째 데이터부터 첫 번째 데이터 기준 좌 혹은 우로, 어떤 위치로 들어갈지 판단한다. 선택정렬보다 속도가 좀 더 빠름
시간복잡도는 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부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j - 1]: # 한 칸씩 왼쪽으로 이동
            array[j], array[j - 1] = array[j - 1], array[j]
        else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break

print(array)

퀵 정렬

기준데이터를(피벗) 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

단, 왼쪽과 오른쪽에서 찾는 값의 위치가 서로 엇갈린 경우 작은 데이터와 피벗의 위치를 서로 변경한다. 이후 왼쪽과 오른쪽 리스트를 개별적으로 정렬시킨다.

퀵 정렬을 재귀 함수로 작성했을 때 끝나는 조건은?

• 리스트의 데이터 개수가 1개인 경우이다.

일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘이다.

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터로 설정한다.

• 퀵 정렬 시간 복잡도
  • 퀵정렬은 평균의 경우 O(NLogN)의 시간 복잡도를 갖는다.
  • 하지만 이미 정렬된 배열에 경우 O(N^2)의 시간 복잡도를 갖는다.

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

def quick_sort(array,start,end):
	if start>=end: # 원소하나일 때 종료
		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[right], array[left] = array[left], array[right]
	# 분할 이후 왼, 오른쪽부분에서 각각 정렬 수행	
	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))

계수 정렬

• 계수 정렬 특정한 조건에서만 사용가능하지만 매우 빠르게 동작하는 정렬 알고리즘

  • 데이터 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

  • 가장 큰 데이터와 작은 데이터 차이가 너무 크면 사용 불가 * 성적 점수 사용 가능!

  • 이유는 ?
    - 모든 범위를 담을 수 있는 리스트를 선언해야하기 때문

    데이터 개수가 N 데이터 중 최댓값이 K일 때 최악의 경우에도 수행시간이 O(N+K)를 보장한다.

    → 인덱스 초기화시키고 정렬할 데이터의 해당 인덱스 개수가 몇 개인지 COUNT한다.

    성적과 같이 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적이다. 0과 9999 2개의 수가 존재한다면 최댓값이 크기 때문에 시간복잡도가 너무 커진다.

    # 모든 원소의 값이 0보다 크거나 같다고 가정
    array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 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=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

sorted()

퀵정렬과 동작 방식이 비슷한 병합 정렬 기반으로 만듬. 퀵보다 느리지만 최악의 경우에도 시간복잡도 O(NLogN)을 보장한다.

정렬 알고리즘 비교하기

정렬 알고리즘	평균 시간 복잡도	공간 복잡도	특징
선택 정렬	O(N^2)	O(N)	아이디어 간단
삽입 정렬	O(N^2)	O(N)	데이터 정렬되어 있을 때 빠름
퀵 정렬	O(NLogN)	O(N)	대부분에 가장 적합, 충분히 빠름
계수 정렬	O(N+K)	O(N+K)	데이터 크기 한정되어있는 경우에는 매우 빠르게 동작