2. 선택 정렬(Selection Sort), 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sorting)

안녕하세요

공상 개발입니다.

 

이번 시간에는 대표적인 정렬 알고리즘인 삽입 정렬, 버블 정렬, 선택 정렬에 대해서 알아보는 시간을 가지겠습니다.

 

---

 

1. 정렬(Sort)의 개요 2. 선택 정렬(Selection Sort) 3. 버블 정렬(Bubble Sort) 4. 삽입 정렬(Insertion Sorting)

 

---

 

# 정렬(Sort)의 개요

 

정렬은 주어진 객체들의 리스트를 정해진 기준으로 순서대로 나열하는 것입니다.

정렬은 정적(static) 집합을 대상으로 합니다.

 # 정적 집합이란, 레코드의 추가 및 삭제, 변경이 없는 경우를 말합니다.

 

대표적인 정렬 알고리즘으로는 아래와 같습니다

삽입정렬, 버블정렬, 선택정렬 병합정렬, 퀵정렬, 힙정렬 기수정렬, 계수정렬, 버킷정렬

 

정렬 알고리즘을 본격적으로 알아보기 전에 안정적(stable) 정렬과 제자리(in-place) 정렬에 대해

간단하게 알아보도록 하겠습니다.

이 특성을 모르고 정렬 알고리즘을 선택한다면, 적합한 결과를 얻지 못할 수도 있기 때문입니다.

 

안정적(stable) 정렬

안정적(stable) 정렬이란, 비교 키가 같은 레코드들의 상대적 순서가 유지되는 정렬을 말합니다. 쉽게 말하면, 정렬되지 않은 상태에서 같은 키값을 가진 원소의 순서가 정렬 후에도 유지가 되는 형태라고 생각하시면 됩니다. 이해를 돕기 위해 아래의 간단한 이미지를 한번 보겠습니다.

 

 

제자리(in-place) 정렬

제자리(in-place) 정렬이란, 추가적인 저장 공간이 입력 크기에 영향을 받지 않는 정렬을 말합니다. 예를 들어 큰 배열을 받았다고 하더라도 큰 메모리 공간이 필요하지 않습니다. 추가적인 저장 공간인 temp(그릇)을 사용해 위치를 바꿔 가면서 정렬을 할 수 있습니다. 제자리 정렬은 자기 자리에서 temp(그릇)을 사용해 위치를 바꿔가며 정렬을 합니다.  temp(그릇)의 이해를 돕기 위해 아래의 간단한 이미지를 한번 보겠습니다. 위의 값들을 정렬한다고 가정합니다. 1. 2를 6의 인덱스와 위치를 바꾸고 싶다. 2. 6을 temp에 담아둔다. 3. 2를 6의 원래 인덱스로 옮긴다. 4. 6을 2의 원래 인덱스로 옮긴다. 5. 이 과정을 반복한다.

 

 단순하지만 비효율적인 방법인 삽입 정렬과 버블 정렬 그리고 선택 정렬에 대해 알아보겠습니다.

---

 

# 선택 정렬(Selection Sort)

 

가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘 시간 복잡도 O(n^2)

 

1. 최솟값을 찾는다.

2. 정렬한다.

 

소스 코드

 

출력 값

 

---

 

# 버블 정렬(Bubble Sort)

 

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보내는 알고리즘 시간 복잡도 O(n^2) 가장 큰 값이 맨 뒤로 이동합니다.

 

버블 정렬은 정렬 알고리즘 중에서 가장 비효율적인 알고리즘입니다.

 

 

출력 값

 

---

 

# 삽입 정렬(Insertion Sorting)

 

각 숫자를 적절한 위치에 삽입하는 알고리즘 시간 복잡도 O(n^2) 정렬이 대부분 되어있다고 가정한다면, 어떤 정렬 알고리즘보다 빠르다.

 

삽입 정렬은 위의 두 정렬과 비교했을 때 조금은 복잡한 구조를 가지고 있다고 생각합니다.

아래의 소스코드를 직접 구현해보는 걸 추천합니다.

 

 

출력 값

 

---

 

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시면 감사하겠습니다.

 

좋은 하루 보내세요.