[알고리즘] 정렬

정렬

정렬이란 우리가 일반적으로 아는 오름차순 정렬, 내림차순 정렬할 때 정렬을 말한다.

정석적인 정의는 이렇다.

 

네이버 국어사전

 

즉 조건에 따라 순서 재배열 하기가 정렬이다.

 

작은 수부터 큰 수까지의 정렬이 오름차순 정렬,

큰 수부터 작은 수까지 정렬이 내림차순 정렬이다.

 

 

 

정렬의 방법

• 내부정렬
• 외부정렬

정렬의 방법에는 내부정렬과 외부정렬이 있다.

내부정렬이 일반적인 정렬이다. 정렬할 데이터가 하나의 배열에 저장될 수 있으면 사용하는 정렬법이다.

외부정렬은 데이터가 너무 많아 하나의 배열에 저장될 수 없는 경우 사용하는 정렬법이다.

 

 

정렬 알고리즘의 핵심 요소

교환, 선택, 삽입이 있고 이 세가지 요소를 이용해 알고리즘을 설계한다.

 

 

정렬의 종류

• 버블 정렬
• 선택 정렬
• 삽입 정렬
• 퀵 정렬
• 병합 정렬
• 힙 정렬

 

📎 버블 정렬

버블 정렬은 맨 끝단부터 이웃한 두 요소의 비교-교환의 과정을 진행하며 정렬하는 알고리즘이다.

 

📎 선택 정렬

선택 정렬은 작은 요소의 순서대로 선택해 앞쪽으로 위치를 옮겨 순서대로 정렬하는 알고리즘이다.

 

📎 삽입 정렬

선택한 요소를 앞쪽의 알맞은 위치로 삽입해 정렬하는 알고리즘

 

버블, 선택, 삽입 정렬의 시간 복잡도는 O(n²)으로 별로 효율적이지 못하다.

이를 좀더 빠르게 처리시키는 정렬이 셸 정렬이다.

 

 

📎 퀵 정렬

퀵 정렬은 정렬 알고리즘 중 가장 빠른 알고리즘으로 일반적으로 사용된다. 

퀵 정렬은 임의의 한 요소를 선택하고 그 요소를 기준(=피벗 :기준으로 하는 요소)으로 그룹을 나눠 정렬하는 작업을 반복하다 그룹원이 모두 1명이 될 경우 정렬이 끝나는 알고리즘이다. 

 

 

📎 병합 정렬

병합 정렬은 정렬을 앞부분과 뒷부분으로 나눈 후 정렬하고, 병합하는 과정을 반복하는 정렬이다. 

 

 

📎 힙 정렬

힙 정렬은 힙(heap)을 사용해 정렬하는 선택 정렬 응용 알고리즘이다.

여기서 힙이란 완전이진트리이다. 

 

 

+참고

책정보, Do it! 자료구조와 함께 배우는 알고리즘 입문 : 네이버 책 (naver.com)

Do it! 자료구조와 함께 배우는 알고리즘 입문

 

+ 전에 공부했던 책인데 기억아 안나는 부분들이 있어 참고했다.

https://book.naver.com/bookdb/book_detail.nhn?bid=13496659 

한 권으로 그리는 컴퓨터과학 로드맵

> 책 후기는 여기..

2020.11.23 - [Hello_World/IT도서] - 한 권으로 그리는 컴퓨터 과학 로드맵 (컴퓨터과학/컴퓨터 이론/컴퓨터구조/비전공자/입문/책추천)