정렬 알고리즘 - 선택 정렬, 삽입정렬, 버블정렬

치맨·2023년 2월 16일

알고리즘

알고리즘,자료구조

목록 보기

10/11

정렬알고리즘을 공부하는 이유

알고리즘에 대해 공부를 하려고 구글 혹은 책을 보면 정렬알고리즘이 우선적으로 나옵니다.
처음에는 그냥 당연하게 공부를 했습니다.
Ex) 그냥 교과서에서 덧셈, 곱셉, 나눗셈 순서대로 나와서 공부하는것 처럼

그러다 문득 왜 정렬 알고리즘을 공부해야할까? 왜 모든사람이, 어느곳에서나 정렬 알고리즘을 우선적으로 배워라 라고 할까? 그렇게나 중요한것인가?? 라는 의문이 생겼습니다.
그래서 인터넷에 이유를 찾아보았습니다.

생각보다 저와같이 의문을 가진 사람들이 꽤 많았고 그분들의 의견을 보고 왜 정렬알고리즘을 공부해야 하는지에 대해 2가지의 이유로 의문이 해결되었습니다.

우선 정렬이 실생활에서 안쓰이는 곳이 없을 정도로 많이 사용하는 알고리즘 입니다.

- 배달앱에서 음식주문을 할때 별점 높은순서, 많이 시켜먹은 순서 등 
- 지도 앱에서 음식점을 검색하면 가까운 거리 순서로 정렬된 결과를 보여줍니다.
- 페이스북은 내가 좋아할만한 게시물 순으로 뉴스피드를 정렬합니다.

많이 사용하니까? 오케이 그렇지만 이미 훌륭한 개발자분들이 정렬 알고리즘 다 만들어놨고, JavaScript에는 이미 내장된 정렬 함수sort()가 있는데, 그걸로 다 해결하면 되지 않을까? 이정도로는 의문이 시원~하게 해결되지 않습니다.

정렬은 알고리즘을 배우는 가장 좋은 교과서이다.

- 이렇게 사용하면 더 빨라지지 않을까?
- 이 아이디어를 적용하면 더 안정적이지 않을까? 
- 같은 정렬이라도 더 빨리 정렬할 수 있지 않을까? 
- 더 효율적으로 정렬 할 수 있지 않을까?
- 시간복잡도는 얼마나 걸릴까?

이런 고민을 하는것이 알고리즘 공부를 하는데 많은 도움이 된다고 합니다.
따라서 정렬알고리즘을 통해 알고리즘에 대해 잘 공부를 한다면 정렬알고리즘에서 뿐만 아니라, 실제 개발을 하면서 맞닥뜨릴 수많은 문제들을 해결하는데 많은 도움을 얻을 수 있을 것 같습니다. 의문이 해결되었으니 정렬 알고리즘에 대해 공부를 해보겠습니다.

선택정렬

선택정렬을 말 그대로 최소값을 선택해서 정렬 하는 것 입니다.
선택정렬은 데이터가 중복된 경우 위치가 바뀔 수 있기 때문에 Unstable한 정렬입니다.
- 예를들어
- 위의 사진에서 4는 하늘색 - 보라색 순서였습니다.
- 정렬 후에는 보라색 - 하늘색 순서로 바뀌게 됩니다.

선택정렬 하는법
- 배열에서 최소값을 찾습니다(선택합니다).
- 최소값을 맨 앞에 위치한 값과 교환합니다.
- 이제 정렬된 맨 앞을 제외하고 다시 순회하며 최소값을 찾습니다.
- 정렬되지 않은 값들 중 첫번째 값과 최소값을 교환합니다.
- 반복

선택정렬 장점

in-place알고리즘으로 메모리가 절약됩니다.
구현하기 쉬운 알고리즘 입니다.

in-place 알고리즘 : 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 알고리즘

선택정렬의 단점

최선의경우, 최악의 경우 모두 O(n^2)이 소요되기 때문에 자료의 개수가 많아질수록 성능이 매우 떨어집니다.

선택정렬 시간복잡도

최선의 경우 : O(n^2)
최악의 경우 : O(n^2)
⇒ 왜 why? 매번 정해진 자리에 올 수 있는 최소값을 찾아야하기 때문입니다.

선택정렬의 이해 돕기

아래의 사진에서

빨간색은 최소값
노란색은 정렬 완료된 값
보라색은 정렬 되지 않은 값

최소값을 찾아 첫번째 값과 바꿔줍니다. 최소값 : 1, 첫번째 5
최소값을 찾아 두번째 값과 바꿔줍니다. 최소값 : 2, 두번째 2
최소값을 찾아 세번째 값과 바꿔줍니다. 최소값 : 3, 세번째 4
최소값을 찾아 네번째 값과 바꿔줍니다. 최소값 : 4, 네번째 4
최종적으로 정렬 완료

선택정렬 JavaScript로 구현하기

삽입정렬

삽입정렬은 정렬되지 않은 배열의 첫번째값을 정렬된 값의 적절한 위치에 삽입하는 정렬입니다.
삽입 정렬은 중복된 데이터는 위치를 교환하지 않기 때문에 stable한 정렬입니다.
삽입정렬 하는법
- 정렬되지 않은 배열의 첫번째값을 찾습니다.
- 정렬된 배열의 적절한 위치에 값을 삽입 합니다.
- 위의 경우를 반복합니다.

삽입정렬 장점

in-place알고리즘으로 메모리가 절약됩니다.
구현하기 쉬운 알고리즘 입니다.
이미 정렬된 데이터를 순회하는 경우 O(n)번만 순회하면 되기 때문에 정렬이 되었는지 안되었는지 테스트하는 용도로 사용될 수 있습니다.

in-place 알고리즘 : 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 알고리즘

삽입정렬의 단점

최악의 경우 O(n^2)이 소요되기 때문에 자료의 개수가 많아질수록 성능이 매우 떨어집니다.

삽입정렬 시간복잡도

최선의 경우 : O(n)
최악의 경우 : O(n^2)
⇒ 왜 why? 정렬이 되어 있는경우는 O(n)이지만, 정렬이 되어 있지 않는경우 O(n^2)의 시간복잡도가 걸립니다.

삽입정렬의 이해 돕기

아래의 사진에서

빨간색은 정렬되지 않은 배열의 첫번째 값
노란색은 정렬 완료된 값
보라색은 정렬 되지 않은 값

정렬되지 않은 배열의 첫번째 값을 찾아 정렬된 배열의 적절한 위치에 삽입 합니다. 첫번째 값 : 5
정렬되지 않은 배열의 첫번째 값을 찾아 정렬된 배열의 적절한 위치에 삽입 합니다. 첫번째 값 : 2
정렬되지 않은 배열의 첫번째 값을 찾아 정렬된 배열의 적절한 위치에 삽입 합니다. 첫번째 값 : 4
정렬되지 않은 배열의 첫번째 값을 찾아 정렬된 배열의 적절한 위치에 삽입 합니다. 첫번째 값 : 3
정렬되지 않은 배열의 첫번째 값을 찾아 정렬된 배열의 적절한 위치에 삽입 합니다. 첫번째 값 : 1
최종적으로 정렬 완료

삽입정렬 JavaScript로 구현하기

버블정렬

버블정렬은 거품이 일어나듯이 연쇄적으로 자기 자리를 찾아간다고 해서 버블 정렬이라고 합니다.
버블정렬은 데이터가 중복된 경우 위치를 교환하지 않고 지나가기 때문에stable한 정렬입니다.
데이터를 2개씩 묶어서 비교한 후 크기가 큰 쪽이 오른쪽으로 가도록 자리를 바꾸기 때문에 n번째 정렬이 끝나면 뒤에서 n번째 데이터들이 정렬 되어있습니다.
버블정렬 하는법
- 앞에서부터 2개씩 요소를 비교합니다.
- 비교를해서 큰 숫자를 오른쪽으로 위치시켜 줍니다.
- 끝까지 2개씩 비교해서 큰수를 오른쪽으로 위치시키는것을 반복해줍니다.

버블정렬 장점

in-place알고리즘으로 메모리가 절약됩니다.
구현하기 쉬운 알고리즘 입니다.

in-place 알고리즘 : 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 알고리즘

버블정렬의 단점

최악의 경우 O(n^2)이 소요되기 때문에 자료의 개수가 많아질수록 성능이 매우 떨어집니다.

버블정렬 시간복잡도

최선의 경우 : O(n)
최악의 경우 : O(n^2)
⇒ 왜 why? 각 자리를 찾기 위해서 n번의 순회를 해야하며, n번의 회전 동안에 요소의 개수만큼 또 순회를 하기 때문에 O(n^2)의 시간복잡도가 걸립니다. 단 정렬이 되어 있는경우 한 번의 순회로 정렬 여부를 알 수 있기 때문에 최선의 경우 O(n)의 시간복잡도가 걸립니다.

버블정렬의 이해 돕기

아래의 사진에서

빨간색은 비교할 첫번째값
초록색은 비교할 두번째값
노란색은 정렬 완료된 값
보라색은 정렬 되지 않은 값

한 칸씩 오른쪽으로 이동하며 왼쪽에서 2개씩 비교해줍니다.
1-1 첫번째 값과 두번째값을 비교해서 큰값을 오른쪽에 둡니다. 비교할 값 : 4,2 큰값 4
1-2. 첫번째 값과 두번째값을 비교해서 큰값을 오른쪽에 둡니다. 비교할 값 : 4,1 큰값 4
1-3. 첫번째 값과 두번째값을 비교해서 큰값을 오른쪽에 둡니다. 비교할 값 : 4,3 큰값 4
한 칸씩 오른쪽으로 이동하며 왼쪽에서 2개씩 비교해줍니다.
1-1 첫번째 값과 두번째값을 비교해서 큰값을 오른쪽에 둡니다. 비교할 값 : 2,1 큰값 2
1-2. 첫번째 값과 두번째값을 비교해서 큰값을 오른쪽에 둡니다. 비교할 값 : 2,3 큰값 3
한 칸씩 오른쪽으로 이동하며 왼쪽에서 2개씩 비교해줍니다.
1-1 첫번째 값과 두번째값을 비교해서 큰값을 오른쪽에 둡니다. 비교할 값 : 1,2 큰값 2