선택 정렬과 삽입 정렬

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소를 가리키는 포인터가 하나 있으며, 첫 번째 요소는 주황색으로 표시되어 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 두 번째 요소를 가리키는 포인터가 하나 있으며, 첫 번째 요소는 주황색으로 표시되어 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 두 번째 요소를 가리키는 포인터가 하나 있으며, 두 번째 요소는 주황색으로 표시되어 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 세 번째 요소를 가리키는 포인터가 하나 있으며, 두 번째 요소는 주황색으로 표시되어 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 네 번째 요소를 가리키는 포인터가 하나 있으며, 두 번째 요소는 주황색으로 표시되어 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 네 번째 요소를 가리키는 포인터가 하나 있으며, 네 번째 요소는 주황색으로 표시되어 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 다섯 번째 요소를 가리키는 포인터가 하나 있으며, 네 번째 요소는 주황색으로 표시되어 있습니다.

최솟값 찾기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 네 번째 요소는 주황색으로 표시되어 있으며, 첫 번째와 네 번째 요소가 교환될 것을 나타내는 두 개의 화살표가 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소는 주황색으로 표시되어 있으며, 첫 번째와 네 번째 요소가 교환되었습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소는 파란색, 두 번째 요소는 주황색으로 표시되어 있으며, 두 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소는 파란색, 두 번째 요소는 주황색으로 표시되어 있으며, 세 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소는 파란색, 두 번째 요소는 주황색으로 표시되어 있으며, 네 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소는 파란색, 두 번째 요소는 주황색으로 표시되어 있으며, 다섯 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색으로 표시되어 있으며, 세 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색, 세 번째 요소는 주황색으로 표시되어 있으며, 세 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색, 세 번째 요소는 주황색으로 표시되어 있으며, 네 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색, 네 번째 요소는 주황색으로 표시되어 있으며, 네 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색, 네 번째 요소는 주황색으로 표시되어 있으며, 다섯 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색, 네 번째 요소는 주황색으로 표시되어 있으며, 세 번째와 네 번째 요소가 교환될 것을 나타내는 두 개의 화살표가 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색, 세 번째 요소는 주황색으로 표시되어 있으며, 세 번째와 네 번째 요소가 교환되었습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색으로 표시되어 있으며, 네 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색, 네 번째 요소는 주황색으로 표시되어 있으며, 네 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색, 네 번째 요소는 주황색으로 표시되어 있으며, 다섯 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색, 다섯 번째 요소는 주황색으로 표시되어 있으며, 다섯 번째 요소를 가리키는 포인터가 하나 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색, 다섯 번째 요소는 주황색으로 표시되어 있으며, 네 번째와 다섯 번째 요소가 교환될 것을 나타내는 두 개의 화살표가 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색, 네 번째 요소는 주황색으로 표시되어 있으며, 네 번째와 다섯 번째 요소가 교환되었습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 파란색으로 표시되어 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬

순서가 없는 숫자 목록의 개략적 표현. 모든 요소가 파란색으로 표시되어 있습니다.

최솟값 찾기
최솟값을 첫 번째 미정렬 요소와 교환하기

선택 정렬 - 구현

def selection_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length - 1):

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

선택 정렬 - 복잡도

최악의 경우: $O(n^2)$
평균의 경우: $\Theta(n^2)$
최선의 경우: $\Omega(n^2)$

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소는 파란색으로 표시되어 있으며, 두 번째 요소가 위로 올라와 있습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째 요소는 파란색으로 표시되어 있으며, 두 번째 요소가 위로 올라와 있습니다. 첫 번째 요소가 오른쪽으로 이동되었습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 두 번째 요소는 파란색으로 표시되어 있으며, 위로 올라왔던 요소가 첫 번째 위치에 놓였습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색으로 표시되어 있습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째와 두 번째 요소는 파란색으로 표시되어 있으며, 세 번째 요소가 위로 올라와 있습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색으로 표시되어 있습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색으로 표시되어 있으며, 세 번째 요소가 위로 올라와 있습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색으로 표시되어 있으며, 세 번째 요소가 위로 올라와 있습니다. 세 번째 요소가 오른쪽으로 이동되었습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색으로 표시되어 있으며, 세 번째 요소가 위로 올라와 있습니다. 세 번째와 두 번째 요소가 오른쪽으로 이동되었습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색으로 표시되어 있으며, 세 번째 요소가 위로 올라와 있습니다. 세 번째, 두 번째, 첫 번째 요소가 오른쪽으로 이동되었습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째 요소는 파란색으로 표시되어 있으며, 세 번째 요소가 위로 올라와 있습니다. 세 번째, 두 번째, 첫 번째 요소가 오른쪽으로 이동되었으며, 위로 올라왔던 요소가 첫 번째 위치에 놓였습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 파란색으로 표시되어 있습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 파란색으로 표시되어 있으며, 다섯 번째 요소가 위로 올라와 있습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 파란색으로 표시되어 있으며, 다섯 번째 요소가 위로 올라와 있습니다. 네 번째 요소가 오른쪽으로 이동되었습니다.

삽입 정렬

순서가 없는 숫자 목록의 개략적 표현. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 파란색으로 표시되어 있으며, 다섯 번째 요소가 위로 올라와 있습니다. 위로 올라왔던 요소가 네 번째 위치에 놓였습니다.

삽입 정렬 - 구현

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

삽입 정렬 - 복잡도

최악의 경우: $O(n^2)$
평균의 경우: $\Theta(n^2)$
최선의 경우: $\Omega(n)$

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘