용어정리
이 카테고리는 비전공자로서 개발자로써 공부하며, 평소 이해하지 못한 단어를 제방식대로 정리하는 카테고리입니다.
제방식대로 풀어 쓴것이므로 오류가 있을 수 있습니다.
오류가 있을시 댓글로 남겨주시면 참고하도록 하겠습니다.
정렬
지난시간에 알고리즘에 대해 알아보았습니다.
알고리즘을 요약하자면, 어떠한 명령어들을 처리하는 과정이라고 하였습니다.
이러한 과정을 함에 있어서 효율적이고 좋은 성능을 통해 개발을 하는 것이 좋은 알고리즘이라고 했었습니다.
지난번 전화번호부를 다시 예로 들어 보겠습니다.
전화번호부책에서 어떠한 부분을 찾는데,
ㄱㅎ까지 AB까지 1~0까지 순서대로 차례로 탐색 또는 검색 방법을 순차적검색 또는 선형탐색이라고합니다.
하지만
ㄱㅎ까지 AB까지 1~0까지 순서가 없이 마구잡이로 섞여있다고 가정을 해봅니다.Q, I, O, P, D, J, A, M, N, S, W, E, Z, X, B, L, H, F, U, T, Y, R
이렇게 정렬되어있지 않은 부분에서 무언가 찾으려면, 시간이 걸립니다.
또한 더 복잡한 데이터안에서 무언가 찾기란 쉽지 않습니다.
그렇기때문에 전화번호부는 AZ까지 ㄱㅎ까지 정렬이 되어있는 것을 볼 수 있습니다.
*’데이터는 원하는 형태로 정렬될 때 비로소 의미 있는 정보가 된다.’*라는 말이 있습니다.
많은 정보를 가지고 있음에도 활용을 하려면 정렬되어 있는 상태로 있어야 그 정보를 활용할 수 있다는 말입니다.
그렇기에 데이터를 활용할때 정렬하는 방법 중 몇가지에 대해 말해보겠습니다.
버블정렬
버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.
단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.
두 개의 인접한 수를 비교하고 만약 순서에 맞지 않는다면 교환해주는 방식으로 작동합니다.
큰값이 점점 끝쪽으로 거품처럼 밀려나간다고 생각하시면, 이해가 빠를것 같습니다.
예를 들어보겠습니다.
5, 1, 6, 2, 4, 3의 리스트를 정렬해보겠습니다.
5, 1, 6, 2, 4, 3 첫번째로 5와 1을 비교해 순서를 정렬합니다.
1, 5, 6, 2, 4, 3 첫번째 정렬이 이루어졌습니다.
다음은
1, 5, 6, 2, 4, 3 5와 6을 비교합니다.
1, 5, 6, 2, 4, 3 비교를 해도 5 < 6 이기때문에 그대로 둡니다.
다음으로
1, 5, 6, 2, 4, 3를 비교합니다.
이러한순서로 정렬이되면,
1, 5, 2, 4, 3, 6 이됩니다.
그러면 다시
1, 5, 2, 4, 3, 6을 비교하고
1, 5, 2, 4, 3, 6을 비교하여
1, 5, 2, 4, 3, 6이런식으로 계속 비교를 하여, 결국
1, 2, 3, 4, 5, 6 으로 최종 정렬이됩니다.
이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.
n개의 요소를 정렬해 주기 위해서는 n-1번 실행해주어야 합니다.
최악의 상황인 경우 최대한의 횟수를 실행해줘야 하므로 경제적이지 않습니다.
선택정렬
선택정렬은 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아
첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다.
예를 들어보겠습니다.
5, 1, 6, 2, 4, 3의 리스트를 정렬해보겠습니다.
5, 1, 6, 2, 4, 3 첫번째로 5와 1을 비교해 순서를 정렬합니다.
1, 5, 6, 2, 4, 3 첫번째 정렬이 이루어졌습니다.
첫번째까지는 버블정렬과 동일합니다.
하지만 선택정렬은 첫 번째 위치(혹은 가장 마지막 위치)의 수가 가장 작은수라는 가정에 의해 이루어집니다.
1, 5, 6, 2, 4, 3을 비교해 5 < 6 이므로 기존을 유지합니다.
1, 5, 6, 2, 4, 3을 비교합니다. 2가 가장 작은 수로 둘의 자리를 바꿔줍니다.
1, 2, 6, 5, 4, 3가 됩니다. 이렇게 두번째 자리까지 정렬이 완료되었다는 가정하에 다음스텝을 진행합니다.
1, 2, 6, 5, 4, *3** 이렇게 세번째 자리의 수와 가장 작은 수를 찾아 자리를 바꾸는 식으로 진행됩니다.
이런식으로 최종적으로
1, 2, 3, 4, 5, 6으로 정렬됩니다.
선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.
버블 정렬의 교환 횟수보다는 적습니다.
그러나 한 번의 교환이 일어나기 위해서는 정렬되지 않은 수의 모든 비교가 이루어져야 하므로, n²번의 비교가 이루어 집니다.
선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교와 교환을 해주어야 합니다.
삽입정렬
삽입정렬은 자료가 정렬된 부분과 정렬되지 않은 부분으로 나누어집니다.
정렬되지 않은 부분의 자료가 정렬된 부분의 자리로 삽입되는 형태의 정렬 방법입니다.
예를 들어보겠습니다.
5, 1, 6, 2, 4, 3의 리스트를 정렬해보겠습니다.
정렬되지 않은 리스트에서 첫번째 가장 작은 수를 찾습니다.
편의상 | 를 사용해 정렬된부분과 정렬되지 않은 부분을 구분합니다.
5, 1, 6, 2, 4, 3 첫번째 제일 작은 수가 정렬됩니다.
1 | 5, 6, 2, 4, 3 정렬되지 않은 부분 중 가장 작은 수를 찾습니다. 1보다 큰수입니다.
1 | 5, 6, 2, 4, 3 5보다는 작습니다.
1, 2 | 5, 6, 4, 3 정렬이됩니다.
1, 2 | 5, 6, 4, 3 다시 가장작은 수를 찾습니다. 정렬된 숫자중 가작 작은수인 1과 비교를 하고 1 < 3이므로 다음으로 넘어갑니다.
1, 2 | 5, 6, 4, 3 다음 정렬된 수와 비교를 합니다. 2 < 3이므로
1, 2, 3 | 5, 6, 4그다음으로 들어갑니다.
이렇게 처음을 제외하고 다음부터는 작은 수를 찾아 정렬된 수와 비교한 후 제자리를 찾아 나머지를 밀어내는 방식으로 정렬됩니다.
삽입 정렬은 특정 실행 단계에서, 어떤 원소가 정렬된 배열 내에 자리를 찾았다고 해서 그것이 최종적인 제자리라는 보장은 없습니다. 다음 단계가 진행되면서 다른 자료에 의해 위치가 바뀔 수 있기 때문입니다. 따라서 삽입 정렬은 자료의 양이 적을 때 성능이 우수하며 자료 대부분이 이미 정렬이 되어있는 경우 효율적입니다. 삽입정렬은 이미 정렬된 자료에 새로운 자료를 삽입해야 하는 경우가 발생하면, 정렬된 자료들이 자리를 이동해야 하므로 안정성이 낮습니다.
합병정렬
합병 정렬은 원소가 한 개가 될 때까지 계속해서 반으로 나누다가 다시 합쳐나가며 정렬을 하는 방식입니다.
합병정렬의 장점은 가장 빠른 정렬방법입니다.
단점은 시간은 가장 빠르게 처리하면서, 메모리를 매우 많이 차지 한다는 점입니다.
바로 예를 들어보겠습니다.
5, 1, 6, 2, 4, 3, 8, 7의 리스트를 정렬해보겠습니다.
편의상 | 를 통해 구분을 하겠습니다.
5, 1, 6, 2, 4, 3, 8, 7 가장 먼저 앞에 두수를 비교해 정렬 후 하나로 합칩니다.
1, 5 | 6, 2, 4, 3, 8, 7 비교를 하지 않은 두수를 비교해 역시 정렬 후 하나로 합칩니다.
1, 5 | 6, 2 | 4, 3, 8, 7 이런식으로 쭉쭉 진행하여
1, 5 | 6, 2 | 4, 3 | 8, 7 이렇게 4개의 리스트로 변경되었습니다.
1, 5 | 6, 2 | 4, 3 | 8, 7 이렇게 두개의 정렬된 데이터를 비교해 정렬 후 합칩니다.
1, 2, 5, 6 | 4, 3 | 8, 7 이런방식으로 일어나는데 다음으로는
1, 2, 5, 6 | 4, 3, 8, 7 이렇게 될 것입니다.
1, 2, 5, 6 | 4, 3, 8, 7 다음엔 또 두개의 리스트를 비교하고
최종적으로 1, 2, 3, 4, 5, 6, 7, 8 하나의 리스트로 정렬하게됩니다.
이렇게 나누어지고 합쳐지는 중간 단계의 배열을 임시로 저장하고 함수가 종료될 때 까지 기억하고 있어야 하기 때문에,
메모리의 필요한 공간이 늘어납니다.
합병 정렬 역시 반을 나눈다는 개념이 사용되기 때문에 시간이 적게 들 것이라고 유추할 수 있습니다.
만약 8개의 원소가 있다면 3번 나누어질 것입니다. 따라서 n개의 원소가 있을 때 완전히 다 나누어지기까지 호출되는 함수의 개수는 log n개라는 것을 알 수 있습니다.
그리고 합병 정렬은 병합하는 알고리즘을 포함합니다.
합쳐지는 과정에서 각 원소들의 크기를 비교하기 때문에 n번의 비교 과정이 있습니다. 즉 한번 나누어질 때마다 n번의 비교 횟수가 추가되는 것입니다.
요즘 같이 성능이 좋은 하드웨어가 많은 경우 합병정렬하는데 무리가 가지 않습니다.
하드웨어의 성능을 고려하며, 상황에 적합하다면 합병정렬을 사용하는 방법이 가장 효율적으로 정렬 할 수 있는 방법입니다.
정리
이처럼 정렬에는 다양한 방법이 있습니다.
버블정렬, 선택정렬, 삽입정렬, 합병정렬 등등…. 다양한방법을 상황에 맞게 올바른 정렬방법을 사용하여,
정보들을 원하는 형태로 정렬하여, 정보를 의미있게 사용하여, 효율적으로 정보전달을 해야합니다.