기술 면접 책정리(정렬)

정렬 알고리즘은 애플리케이션의 성능에 지대한 영향을 끼칠 수 있다.

선택 정렬

가장 단순한 정렬 알고리즘 가운데 하나로 꼭힌다. 배열의 첫 번째 원소에서 시작하여 배열 전체를 훑으면서 가장 작은 키를 가지는 원소를 찾아서

첫번쨰 원소와 맞 바꾼다. 그 다음 두번째 원소로 넘어가면서 마지막 원소에 이르기까지 같은 작업을 반복한다.

최선 평균 최악 모두 정렬은 O(n^2)이다.  처음 시작할때의 정렬 상태는 비교횟수에 전혀 영향을 미치지 못한다.

처음 정렬상태랑 무관하게 O(n^2)이다.

버블 정렬

정렬전 상태에 따라서 이동 연산의 횟수에 차이가 있다. 자료가 먼저 완전 정렬히 되어있다면(원하는 방향으로) 자료의 이동 연산은 0회 발생..

근데 효율성 자체가 비교와 이동의 더하기 이기 떄문에 항상 최선 평균 최악 O(n^2)이다.

삽입정렬

마치 카드를 정렬 할때와 마찬가지로 한 번에 한 원소씩 이미 정렬된 다른 원소들과 비교하여 새 원소를 제위치에 삽입하는 식으로 정렬된 배열을 만듬

선택정렬하고 다르게 삽입 정렬은 최선의 경우 (이미 정렬된 상태라면) O(n)이다. 이미 정렬된 리스트에 새 원소를 추가할 때는 삽입 정렬이 매우 효율적이다. 왜냐면 각 정렬 단계에서 1번씩의 비교만 필요하고 이동 연산이 필요없으므로 O(n) 효율성을 가진다. 그러나 무작위로 정렬된 최악은 O(n^2)이다.

삽입 정렬은 안정적이면서 제자리 정렬 알고리즘으로 소량의 데이터 집합을 처리할 때 강점을 발휘하기 때문에 다른 더 복잡한 정렬 알고리즘을

만드는 기본 단위로 많이 쓰임..

void InsertSort(int* array, int iSize)

{

for (int i = 1; i < iSize; ++i)

{

int temp = 0;

int current = i;

while (current >= 0)

{

if (array[current] < array[current - 1])

{

temp = array[current];

array[current] = array[current - 1];

array[current - 1] = temp;

}

--current;

}

}

삽입 정렬을 개선한 쉘정렬(최선 O(n), 평균 O(n^1.25), 최악 O(n^2)

void SellSort(int* array, int iSize)

{

int count = (iSize) / 2;

while (count >= 1)

{

for (int i = 0; i < count; ++i)

{

for (int j = i + count; j < iSize; j = j + count)

{

int temp = array[j];

int current = j;

while ((current >= i) && (array[current - count] > temp))

{

array[current] = array[current - count];

current -= count;

}

array[current] = temp;

}

}

count /= 2;

}

}

퀵 정렬

퀵 정렬 데이터 집합 내에서 한 피벗 값을 고른다음 그걸 기준으로 집합을 두개의 부분집합으로 나눈다.

한쪽 부분은 피벗보다 작은, 다른한쪽은 피벗보다 큰것만 넣는다..

재귀적으로 더이상 쪼개지 못할때까지 함..

퀵 정렬은 가장 이상적인 피벗값은 전체 데이터를 절반씩으로 쪼갤 수 있는 값이다.

각 원소에 대해 상수 시간 연산을 횟수는 n을 1이 나올때까지 반복해서 2로 나누는 횟수 log(n)이다.

n개의 원소에 대해 log(n)번씩 연산을 수행하니까 nlog(n)이다.

최악은 O(n^2)이다 리스트 처럼 쏠리게 된다면..

완전히 정렬이 안된 상탠 무작위적인 데이터라면 피벗 값이 위치와 무관하기 때문에 어떤 피벗 값을 선택하든 차이가 없는데..

하지만 데이터가 어느정도 정렬되어있는 상태라면 O(nlog(n))복잡도가 보장된다. 보통 그래서 중앙값 선택한다..

// datastructtest.cpp : 콘솔 응용 프로그램에 대한 진입점을 정의합니다.

//

#include "stdafx.h"

int PivotCal(int* array, int iFirst, int iLast)

{

//책에서는 여기에 first + (size / 2) 이렇게 구했는데..

//결국 이게 밑에랑 같은거다. 

int iMid = (iFirst + iLast) / 2;       

//반드시 삼중앙 값을 찾을때 가장 작을 수를 확인하고 진행해야한다..

//여기서 보면 First가 가장 작을 경우부터 처리한다.

if ((array[iFirst] < array[iMid])

&& (array[iFirst] < array[iLast]))

{

if (array[iMid] > array[iLast])

return iLast;

else

return iMid;

}

if ((array[iMid] < array[iFirst]) 

&& (array[iMid] < array[iLast]))

{

if (array[iFirst] > array[iLast])

return iLast;

else

return iFirst;

}

if (array[iMid] > array[iFirst])

return iFirst;

else

return iMid;

}

void QuickSort(int* array, int iFirst, int iSize)

{

//사실 그냥 이 함수를 if로 크게 iSize > 1이렇게 해도된다!

if (iSize == 1 || iSize == 0)

return;

//왜 사이즈 -1 하는지 알지? 직접계산해봐라..전체크기랑 인덱스랑은 다르다;

int iLast = iFirst + (iSize - 1);

int iPivot = PivotCal(array, iFirst, iLast);

int iLeft = iFirst;

int iRight = iLast;

//피봇위치에 맨 처음 값을 넣고..

//이유는 알지? 오른쪽 부터 내려오니까 앞에 값이 비어도되..그러면서 Pivot값은 따로 보관한다.

int iPivotValue = array[iPivot];

array[iPivot] = array[iFirst];   

while (iLeft < iRight)

{

while(iRiht > iLeft)

{

if (array[iRight] < iPivotValue)

{

array[iLeft] = array[iRight];

iLeft++;

break;

}

else

--iRight;

}

while (iLeft < iRight)

{

if (array[iLeft] > iPivotValue)

{

array[iRight] = array[iLeft];

--iRight;

break;

}

else

++iLeft;

}

}

array[iLeft] = iPivotValue;

//재귀 함수 호출

QuickSort(array, iFirst, iLeft - iFirst);

QuickSort(array, iLeft + 1, iLast - iLeft);

}

int main()

{

int array[13] = { 11, 10, 16, 4, 8, 12, 1, 6, 0, 20, 2, 9, 5 };

QuickSort(array, 0, 13);

return 0;

}

합치기 정렬

머지 정렬 (합치지 정렬) 데이터 집합을 둘 이상의 부분 집합으로 가르고, 각 부분집합을 정렬한 다음 부분집합을 다시 정렬된 형태로 합치는 방식이다.

데이터 집합이 메모리에 한 번에 올리기에 넘 너무 클 때 쓰기 좋은 방법이다? 최고 최저 평균 모두 O(nlog(n))이다. 좋은데 단, 다른 알고리즘 대비 O(n)수준의 메모리가 추가로 필요하다.

---

정렬할때 가장 적합한 알고리즘은??

무조건 퀵 정렬이라고 대답하면 안됨....알고리즘들이 장단점이 많기 때문이다..

되물어야 할것

1. 어떤 데이터인가? 

  - 데이터가 이미 거의 정렬된것인가? 데이터의 크기는? 중복된 키가 있을 수도 있나?

2. 정렬 조건이 어떻게 되나?

  - 최선, 최악, 평균 어느 상황에 맞춰야 하나? 안정성을 만족시켜야 하나?

*여기서 안정성이란 : 안정적인 정렬 알고리즘이란 키가 같은 원소의 순서를 입력된 순서 그대로 유지시켜주는 정렬 알고리즘을 뜻한다.

정렬되지 않은 키가 정렬되고 있는 키가 있던 자리로 맞바뀌어 들어가면서 그 정렬되지 않은 키의 

다른 정렬되지 않은 키들에 대한 상대적인 위치 정보를 잃어버리고 말기 때문이다. 

단순히 int배열 정렬에 대해서는 안정적인 정렬과 불안정한 정렬을 구분하기 어렵다. 왜냐면..이 안정적이라는건...

더 큰 정렬의 데이터에서 활용되는데.. 객체의 한 부분을 키로 잡아서 쓸때만 그 차이점이 나타나기 때문이다..

* 키 값이 똑같아도 객체 전체가 똑같은건 아닌 상황에서만 의미가 있다.

3. 어떤 시스템인가?

  - 정렬해야 하는 데이터의 

---

정렬 알고리즘은 최적, 평균, 최악 조건에서의 성능은 물론, 메모리 사용이나 안정성 등으 ㅣ범주를 기준으로 골라서 써야 한다.

비교를 기반으로 한 정렬알고리즘은 최악 조건의 속드는 절대 O(nlog(n))보다 빠를 수 없다.

선택은 가장 단순하지만 어떤 조건에서도 O(n^2) 를 보여준다.

하지만 맞 바꾸는 횟수 O(n)이기 때문에 복사 연산이 매우 느린 경우에 적합..

삽입 정렬은 대부분이 이미 정렬된 데이터 집합에 대해 매우 효율적 이어서 O(n)까지 나올 수 있지만, 평균 및 최악 조건에서는 O(n^2)이다.

퀵 정렬은 최적 및 평균 조건은 O(nlog(n))인데 최악은 O(n^2)이다.  

병합(합치기) 정렬은 분할정복 알고리즘(퀵도 분할)인데 어떤 조건에서도 O(nlog(n)) 성능이 나온다. 메모리에 전부 집어 넣을 수 없는 데이터

집합을 정렬할 때 특히 유용하다.

모든 알고리즘을 안정성있게 하는 방법은 각 원소마다 순서를 지정하기 위한 일련번호를 붙인 다음 다중키 정렬에서

그 일련번호를 가지고 일차 키가 같은 원소를 구분하면 어떤 정렬 알고리즘이든 안정적으로 돌아가게 만들 수 있다.

---

어느정도 데이터가 정려