전체 방문자
오늘
어제
모달조아
Better than yesterday
모달조아
  • 분류 전체보기 (147)
    • PS (86)
      • BOJ (79)
      • 프로그래머스 (6)
    • 이론 (41)
      • 자료구조 (2)
      • 알고리즘 (8)
      • 데이터베이스 (1)
      • 운영체제 (1)
      • 네트워크 (3)
      • 디자인패턴 (7)
      • Java (13)
      • Spring (4)
      • JPA (1)
      • Git (1)
    • 개발 (18)
    • 프로젝트 (1)
    • 기록 (0)
      • 후기 (0)
    • etc (1)

최근 글

티스토리

hELLO · Designed By 정상우.
모달조아
이론/알고리즘

기본 정렬(선택 정렬, 버블 정렬, 삽입 정렬)

이론/알고리즘

기본 정렬(선택 정렬, 버블 정렬, 삽입 정렬)

2021. 7. 10. 00:43

목차

  1. 선택 정렬(Selection sort)
    1-1. 선택 정렬이란?
    1-2. 선택 정렬 구현
  2. 버블 정렬(Bubble sort)
    2-1. 버블 정렬이란?
    2-2. 버블 정렬 구현
  3. 삽입 정렬(Insertion sort)
    3-1. 삽입 정렬이란?
    3-2. 삽입 정렬 구현
  4. 시간복잡도 비교

1. 선택 정렬(Selection sort)

1-1. 선택 정렬이란?

자리가 정해져 있는 정렬 알고리즘이다. 주어진 배열이나 리스트에서 최솟값을 찾고 그 값을 맨 앞의 값과 위치를 바꾼다. 같은 방법으로 나머지 값들을 정렬한다. 아래에 8, 5, 1, 3, 6이 담겨 있는 배열을 선택 정렬로 정렬해보자.

우선, 제일 앞에 있는 8의 위치를 i라고 하고, j는 i다음 위치부터 존재하는 최솟값의 위치를 가져온다. 그리고 그 위치를 minidx라고 하자.
j가 5부터 minidx를 찾아보니 1이 있는 자리가 가장 작다. 그러므로, minidx는 2가 되고 8과 1의 위치를 바꿔준다.

그 후에, i는 1 증가하여 두번째 자리가 되고, j는 배열을 검색하여 minidx를 3이 있는 위치인 3으로 지정한다. 그리고 i와 minidx의 위치를 바꿔준다.

이 과정을 계속 반복해주면 된다. 그림으로 과정을 살펴보자.



1-2. 선택 정렬 구현

#include <iostream>
using namespace std;
int arr[5] = { 8,5,1,3,6 };
void swap(int* a, int* b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void SelectionSort(int arr[], int size)
{
int minidx;
for (int i = 0; i < size - 1; i++)
{
minidx = i;
for (int j = i + 1; j < size; j++)
{
if (arr[j] < arr[minidx]) minidx = j;
}
swap(arr[i], arr[minidx]);
}
}
int main(void)
{
SelectionSort(arr, 5);
for (int i = 0; i < 5; i++) cout << arr[i] << ' ';
}

2. 버블 정렬(Bubble sort)

2-1. 버블 정렬이란?

버블 정렬이란 인접한 위치의 원소를 비교하여 조건에 알맞으면 교환하는 방식으로 정렬하는 방법이다. 예를 들자면, 0번째 원소와 1번째 요소를 비교하여 조건에 맞으면 교환하고, 1번째 요소와 2번째 요소를 비교하여 조건에 맞으면 교환하는 것을 계속 반복하는 것이다. 아래 그림의 배열을 버블 정렬로 정렬해보자.

인덱스를 j라고 하자. j와 j+1에 담긴 원소를 비교하여 j에 담긴 원소가 j+1에 담긴 원소보다 더 크면 위치를 바꿔준다. 여기서는 8이 5보다 크니까 위치를 바꿔준다.

그 다음에는 j를 1 증가시키고 8과 1을 비교한다. 8이 1보다 더 크니 위치를 바꾼다. 즉, 큰 원소를 오른쪽으로 계속 보내는 방식으로 정렬하는 것이다.

그림으로 나머지 과정들을 살펴보자.



그 후, 다시 j는 0으로 돌아가서 3까지 위 과정을 반복해주고, 다시 j가 0으로 돌아가서 2까지 위 과정을 반복해주는 방식을 반복하여 정렬해준다.

2-2. 버블 정렬 구현

#include <iostream>
using namespace std;
int arr[5] = { 8,5,1,3,6 };
void swap(int* a, int* b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}
void BubbleSort(int arr[], int size)
{
for (int i = size - 1; i > 0; i--)
{
for (int j = 0; j < i; j++)
{
if (arr[j] > arr[j + 1]) swap(arr[j], arr[j + 1]);
}
}
}
int main(void)
{
BubbleSort(arr, 5);
for (int i = 0; i < 5; i++) cout << arr[i] << ' ';
}

3. 삽입 정렬(Insertion sort)

3-1. 삽입 정렬이란?

삽입 정렬은 원소 중 하나를 key로 지정하여, key를 알맞은 위치에 삽입하는 방식이다. key보다 앞의 원소들과 key를 비교하여, key보다 큰 값들은 한 칸씩 뒤로 보내고, key보다 작은 값을 만나면 그 뒷자리에 key를 삽입하는 것이다. 아래 그림의 배열을 삽입 정렬로 정렬해보자.

key는 두번째 원소, 인덱스 값이 1인 위치부터 시작이다. key보다 앞의 원소들과 key를 비교해야하는데, key가 제일 앞의 원소이면 안되기 때문이다.

8보다 작은 원소가 없으므로 제일 앞에 삽입하고, key가 한 칸 앞으로 가 1이 key가 된다.

위와 같은 과정을 계속 반복해주며 정렬한다. 그림으로 남은 과정들을 보자.



3-2. 삽입 정렬 구현

#include <iostream>
using namespace std;
int arr[5] = { 8,5,1,3,6 };
void InsertionSort(int arr[], int size)
{
int key, j;
for (int i = 1; i < size; i++)
{
key = arr[i];
j = i - 1;
while ((j >= 0) && (arr[j] > key))
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
int main(void)
{
InsertionSort(arr, 5);
for (int i = 0; i < 5; i++) cout << arr[i] << ' ';
}

4. 시간복잡도 비교

선택 정렬과 버블 정렬은 항상 O(N^2)의 시간복잡도를 가진다. 하지만 삽입 정렬은 이미 정렬되어있는 배열이 입력으로 들어오면 O(N)의 시간복잡도를 가진다. 바로 key보다 작은 원소들을 만나기 때문이다.

저작자표시 (새창열림)

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

시간 복잡도 / 공간 복잡도  (0) 2021.08.12
위상 정렬(Topological sorting) [Java]  (0) 2021.08.07
투 포인터  (0) 2021.07.24
그리디 알고리즘  (0) 2021.07.18
이분탐색(Binary search)  (0) 2021.07.11
  • 목차
  • 1. 선택 정렬(Selection sort)
  • 2. 버블 정렬(Bubble sort)
  • 3. 삽입 정렬(Insertion sort)
  • 4. 시간복잡도 비교
'이론/알고리즘' 카테고리의 다른 글
  • 위상 정렬(Topological sorting) [Java]
  • 투 포인터
  • 그리디 알고리즘
  • 이분탐색(Binary search)
모달조아
모달조아

티스토리툴바

단축키

내 블로그

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

블로그 게시글

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

모든 영역

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

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