정렬

삽입 정렬

데이터를 하나씩 확인 하면 적절한 위치에 삽입하자.

삽입 정렬은 두 번째 데이터부터 시작. 첫 번째 데이터는 정렬되어 있다고 생각하는 것.

현재 인덱스의 숫자와. 비교를 하는 숫자중 현재 인덱스의 숫자가 작으면 스왑을 하자.
두 번째 인덱스부터 마지막 인덱스 까지 확인이 필요함.

for i in range(1, len(number)):
    for j in range(i, 0, -1):
    # 파이썬의 경우 (start, end, step)의 순서로 end - step 까지 반복한다.

지속적인 비교가 필요하기 때문에 2번째 반복문에서 비교를 해야하는 값은 i번째 인덱스 요소값이다.
i번째 인덱스 값을 j 를 이용하여 계속해서 계산할수 있도록 하자.

if number[j] < number[j - 1]:
    number[j], number[j - 1] = number[j - 1], number[j]

조건으로 현재 숫자, 비교숫자 중 현재 숫자가 작으면 스왑을 함.
현재 숫자가 크면 반복을 종료하고. 다음 인덱스로 이동.

else
    break

시간 복잡도 O(N²)

선택 정렬

현재의 리스트에서 가장 작은 값을 맨 앞 인덱스와 교체하자.

교체한 인덱스의 경우에 정렬된것이기 때문에, 없는 취급 한다.

최솟값을 기록할 변수 필요하다.
매 반복마다 최솟값은 다르다..

for i in range(len(number)):
	min = 999

현재의 인덱스 = 0 전체 리스트를 순회 하며 최솟값을 찾고 인덱스를 저장한다..

    for j in range(i, len(number)):
        if min > number[j]:
            min = number[j]
            index = j

최솟값을 찾기 위한 반복이 끝난 후에 스왑을 한다.

    number[i], number[index] = number[index], number[i]

시간 복잡도 O(N²)

퀵 정렬

Divide conquer combine 으로 순서를 나눌 때

divide를 하며 conquer를 해버린다. 이를 Partition 함수로 나타낸다.

---

Partition 함수
input : 정렬할 숫자_리스트, 시작 인덱스, 마지막 인덱스
현재 리스트의 마지막원소, 피봇으로 잡는다.
모든 리스트의 값을 비교해 피봇보다 큰 값, 작은 값으로 나눈 후 반복할 것이다.
큰 값의 시작 인덱스인 b, 반복을 위한 i를 만든다.

    pivot = 숫자_리스트[마지막 인덱스]
    b = 시작 인덱스
    i = 시작 인덱스

반복문의 조건 : 반복이 피봇까지 행해 졌을 때
반복을 행하다가 피봇 보다 작은 값을 발견 했을 때, b 인덱스의 값과, i를 교체 할 경우
리스트의 제일 앞에서 부터는 피봇보다 작은 값들이 정렬.
그 뒤로는 큰 값들이 정렬 되게된다.

    while i < 마지막 인덱스:
        if 숫자_리스트[i] < pivot:
            number[i], number[b] = number[b], number[i]
            b += 1
            # b 의 값을 1개 옮김으로 다시 피봇 보다 큰 값의 시작점을 가리킴.
        i += 1

모든 반복이 완료된 후에는 피봇보다 작은 값들, pivot, 피봇보다 큰 값들 로 정렬을 해야함.
b번 인덱스와. 마지막 인덱스의 값을 스왑하는 것으로 정렬 가능.

    number[마지막 인덱스], number[b] = number[b], number[마지막 인덱스]
    return b

---

Divide를 위한 quicksort 함수
input : 정렬할 숫자 리스트, 시작 인덱스, 마지막 인덱스

재귀의 종료조건은 입력 받은 숫자 리스트의 길이가 1보다 작을 때.

    if 마지막 인덱스 - 시작 인덱스 < 1:
        return

partiton 함수를 이용해서 정렬, 피봇의 인덱스를 받음.

    b = partition(정렬할 숫자 리스트, 시작 인덱스, 마지막 인덱스)

피봇보다 작은 리스트에대한 퀵정렬, 피봇보다 큰 리스트에 대한 퀵정렬 수행.

    quicksort(정렬할 숫자 리스트, 시작 인덱스, b - 1)
    quicksort(정렬할 숫자 리스트, b + 1, 마지막 인덱스)

시간 복잡도 : O(NlogN)

병합 정렬

Divide conquer combine 으로 순서를 나눌 때

conquer와 combine가 동시에 이루어짐. 이를 Merge 함수로 나타낸다.

---

Merge 함수
input : 정렬할 list1, 정렬할 리스트 2

나중에 정렬된 리스트를 리턴해주기 위한 빈리스트, list1의 인덱스 나타낼 i, list2의 인덱스 나타낼 j를 생성.

    merged_list = []
    i = 0
    j = 0

만약 입력 받은 리스트 둘중에 하나라도 빈 리스트 일 경우에는 정렬이 필요없기에 리턴 해주자.

    if len(list1) == 0 or len(list2) == 0:
        return list1 + list2

반복은 두 리스트의 인덱스를 나타내는 것중 하나라도 len(list)의 길이와 같아 질때 까지 반복.
두 리스트의 요소들을 비교해서 작은 값 부터 merged_list에 append 하여준다.
값이 동일한 경우에는 둘 다 저장하고 i와 j값을 +1씩 해준다.

    while i < len(list1) and len(list2) == 0:
        if list1[i] > list2[j]:
            merged_list.appen(list2[j])
            j += 1
        elif list1[i] < list2[j]:
            merged_list.appen(list1[i])
            i += 1
        else:
        # 값이 같을 경우
            merged_list.appen(list2[j])
            merged_list.appen(list2[j])
            i += 1
            j += 1

이후에 인덱스가 리스트 길이와 같지 않은 것을 찾아 슬라이싱으로 추가해주자.

    if i == len(list1):
        return merged_list + list2[j:]
    elif j == len(list2):
        return merged_list + list1[i:]

---

Merge Sort 함수
input : 정렬할 숫자 리스트.
Divide부터 해야 한다. (반반 계속 찢어주기)

    middle = len(숫자 리스트) // 2
    first_half = 숫자리스트[: middle]
    second_half = 숫자리스트[middle:]

Merge sort 도 재귀를 이용해서 부를 건데 종료 조건은 입력 받은 리스트가 길이가 1일때 리턴.

    if len(숫자 리스트) < 2:
        return 숫자 리스트

인제 찢는것과 동시에 합쳐 주자.

    return Merge(merge_sort(first_half), merge_sort(second_half))

시간 복잡도 : O(NlogN)