버블 정렬
-
선택 정렬이 불안정 정렬인 이유 :: 마이구미알고리즘 2017. 1. 13. 00:07
이번 글은 선택 정렬이 불안정 정렬인 이유에 대해 다뤄본다.그에 앞서 증명을 위해 버블 정렬, 선택 정렬, 삽입 정렬을 언급하겠다. 3가지를 드는 이유는 특별한 건 없다.단지 가장 구현하기 쉽고, 이해하기 쉬운 정렬이기 때문이다.(세가지 모두 시간 복잡도는 O(n^2) 이다.) 버블 정렬 선택 정렬 삽입 정렬세가지 정렬은 어렵지 않기 때문에 위키의 도움을 빌리겠다. 안정 정렬과 불안정 정렬이라는 말을 들어봤을 것이다.안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되는 정렬 방식 ( 버블 정렬, 삽입 정렬 )불안정 정렬 - 동일한 값에 대해 기존의 순서가 유지되지 않는 정렬 방식 ( 선택 정렬 )위와 같이 무슨 뜻인지만 알고 있는 경우가 많다.왜? 질문을 던지면 선뜻 증명을 못하면 문제가 있다.많은 글..
-
백준 1377번 버블 소트:: 마이구미알고리즘 풀이/정렬 2016. 12. 28. 22:52
이번 글은 백준 알고리즘 사이트의 1377번 "버블 소트" 를 다뤄본다.정답률은 20% 대로, 200명정도이다.1377번 버블 소트 - https://www.acmicpc.net/problem/1377 이미 문제에서도 버블 소트의 소스를 보여줬다.출력되는 정답이 의미하는 건 버블 정렬이 몇단계를 거쳤는지를 알아내는 것이다.버블 정렬을 잠깐 살펴보자. (기본적으로 버블 정렬을 숙지하고 있다고 가정하겠다.)다음과 같이 주졌다고 하자. (10 4 2 5 9 1)10 4 2 5 9 1 -> 4 10 2 5 9 1 -> 4 2 10 5 9 1 -> 4 2 5 10 9 1 -> 4 2 5 9 10 1 -> 4 2 5 9 1 10위의 경우가 1단계라고 하자.그렇다면 다음이 2단계라고 할 수 있다.4 2 5 9 1 1..