[인프런] 영리한 프로그래밍을 위한 알고리즘 강좌

 

섹션 3. 정렬(Updated)

• 기본적인 정렬 알고리즘
• 합병 알고리즘(merge sort)

 

1월 30일 늦은 시간 인강을 들었다보니 글을 쓰기전에 하루가 지나 버렸다...

인프런의 영리한 프로그래밍을 위한 알고리즘 강좌 섹션 3의 정렬 강의를 들었다.

기본적인 정렬 알고리즘의 종류는 이미 대학교 알고리즘 수업을 통해 접해봐서 어렵지는 않았다.. 다만 피곤해서 강의를 많이 듣는것이 힘들었다.

두 가지 강의를 통해 백준 알고리즘을 풀어보았다.

두 알고리즘의 작성해보는 정도인 문제로

develop-recode.tistory.com/19

[BOJ] 정렬 단계

자세한 내용은 위의 링크를 통해 확인 할 수 있다.

기본적인 정렬 알고리즘

▷ Select sort

Select sort의 경우 가장 큰 값을 사용하여 배열의 마지막 값과 위치를 변경하는 정렬 방법이다.

data 배열

3

2

4

5

1

▽

3

2

4

5

1

가장 큰 값 5를 선택하여 마지막 값인 n-1자리의 값과 교환한다.

▽

3

2

4

1

5

가장 큰값이 마지막 위치로 이동했기 때문에 더이상 배열의 n-1번째는 고려하지 않는다.

이러한 식으로 가장 큰값의 위치를 옮겨 정렬하고, n-1번씩 비교하여 시간 복잡도는 T(n) = (n-1) + (n-2) + ... + 2 + 1 = O(N**2)가 된다.

▷ Bubble sort

Bubble Sort의 경우 가장 첫번째 index값과 그 다음값을 비교하여 서로의 위치를 교환하여 정렬하는 방법이다.

data 배열

3

2

4

5

1

▽

3.

2.

4

5

1

첫번째 인덱스 값과 두번째 인덱스 값을 비교하여 큰값을 뒤로 보낸다.

▽

2

3

4

5

1

따라서 2와 3의 위치가 바뀐다.

▽

1

3

4

5

2.

2는 또 다음값들과 비교되어 마지막에는 1과 자리가 바뀌게 된다.

이러한 식으로 끝까지 확인되어 바뀌면 1번째 인덱스는 고려하지 않는다.

이 또한 n-1번씩 비교하여 시간복잡도는T(n) = (n-1) + (n-2) + ... + 2 + 1 = O(N**2)가 된다.

▷ Insert Sort

Insert Sort의 경우 정렬된 배열에서 한 값이 입력되었을 때 그 값을 정렬할 때 사용하기 좋다.

data 배열

2

3

5

6

7

8

4

9

위와같은 배열이 있을 때 4의 위치를 정렬하고 싶다. 이때 앞에있는 인덱스의 값과 비교하여 위치를 앞으로 넣어준다.

▽

2

3

5

6

7

4

8

9

이러한 방법을 통해 4는 위치가 앞으로 이동되면 3과 비교되어 큰값이므로 더이상 앞으로 이동하지 않고 더이상 값을 비교하지 않아도된다.

Insert Sort의 시간복잡도의 경우 최악의 경우 O(N**2)시간이 걸리며 빠르면 O(N)의 시간복잡도로 나타낼 수 있다.