선택 정렬 & 삽입 정렬

2023. 11. 3. 16:56· Python/알고리즘 - 이론
목차
  1. 정렬
  2. 선택 정렬
  3. 선택 정렬의 시간 복잡도
  4. 삽입 정렬
  5. 삽입 정렬의 시간 복잡도
  6. Reference
반응형

정렬

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열한 것이다.

일반적으로 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다.

 

선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

  1. 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 가장 앞의 데이터와 바꾼다.
  2. 앞선 1번의 과정을 반복한다.
  3. 정렬되지 않은 데이터가 하나가 남은 경우 처리하지 않아도 완성이 된다.
array = [7, 3, 5, 4, 2, 6, 1, 0]

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)

 

선택 정렬의 시간 복잡도

선택 정렬은 N번만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.

구현 방식에 따라서 사소한 오차는 있을 수 있지만, 전체 연산 횟수는 아래와 같다.

N+(N-1)+(N-2)+...+2

이는 빅오 표기법에 따라서 O(N**2)이라고 작성한다.

 

삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입한다.

선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 동작한다.

  1. 앞쪽의 원소는 이미 정렬되어 있다고 가정하고 다음 데이터가 어디 위치로 들어갈지 판단한다.
  2. 다음 데이터를 왼쪽 데이터와 비교하여 위치를 판단한다. (현재 위치가 자기 위치일 때까지 왼쪽 데이터와 비교)
array = [7, 3, 5, 4, 2, 6, 1, 0]

for i in range(1, len(array)):
    for j in range(i, 0, -1):
        if array[j] < array[j-1]:
            array[j], array[j-1] = array[j-1], array[j]
        else:
            break
            
print(array)

 

삽입 정렬의 시간 복잡도

삽입 정렬의 시간 복잡도는 O(N**2)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용된다.

삽입 정렬은 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다.

  • 최선의 경우 O(N)만큼의 시간 복잡도를 가진다.

 

Reference

 

반응형
저작자표시 (새창열림)

'Python > 알고리즘 - 이론' 카테고리의 다른 글

계수 정렬  (0) 2023.11.07
퀵 정렬  (0) 2023.11.05
DFS  (0) 2023.10.24
재귀함수  (0) 2023.10.22
스택과 큐 자료구조  (1) 2023.10.21
  1. 정렬
  2. 선택 정렬
  3. 선택 정렬의 시간 복잡도
  4. 삽입 정렬
  5. 삽입 정렬의 시간 복잡도
  6. Reference
'Python/알고리즘 - 이론' 카테고리의 다른 글
  • 계수 정렬
  • 퀵 정렬
  • DFS
  • 재귀함수
Jong_seoung
Jong_seoung
기록하자, 머리는 생각하는 곳이지 저장장치가 아니다.
Today_developStory기록하자, 머리는 생각하는 곳이지 저장장치가 아니다.
반응형
Jong_seoung
Today_developStory
Jong_seoung
전체
오늘
어제

블로그 메뉴

  • Home
  • Git Hub
  • 분류 전체보기 (351)
    • Theory (16)
    • Java (3)
      • 알고리즘 (2)
      • 문법 (0)
    • Spring (7)
      • 스프링 입문 (6)
      • PickTalk (0)
      • 에러처리 (1)
    • Python (80)
      • 알고리즘 - 이론 (17)
      • 알고리즘 - 내장함수, 라이브러리 등등 (3)
      • 알고리즘 - 백준 (53)
      • 나도코딩 정리 (2)
      • 기타 (5)
    • Django (159)
      • DRF (105)
      • 인프라 (46)
      • DataBases (2)
      • API Docs (6)
    • FrontEnd (22)
      • htmx (2)
      • React (8)
      • 자바스크립트 (12)
    • GIT (16)
    • 기타 (8)
      • 정리 (2)
      • Flutter (1)
      • 마이크로프로세서 - ATmega128 (2)
      • 개발환경 세팅 (3)
    • 자격증 (37)
      • 정보처리기사 (19)
      • SQLD자격증 (18)

인기 글

최근 글

태그

  • alarm
  • BFS
  • CSRF
  • Django
  • django channels
  • django sse
  • django tutorial
  • django 배포
  • django 스웨거 적용
  • Django 이미지 저장

최근 댓글

hELLO · Designed By 정상우.v4.3.0
Jong_seoung
선택 정렬 & 삽입 정렬
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.