[1014] 평균, 최악 선형시간 선택 알고리즘

평균 선형시간 선택 알고리즘과, 최악 선형시간 선택 알고리즘을 구현해보았다.

이번 과제의 목표는 앞서 배웠던 퀵소트를 부분적으로 활용하여 해결하였다. 이번 과제에서 탐색의 주요 부분의 역할을 했던 것은 범위 안의 원소들을 정렬하는 partition함수였다. 배열, 배열의 시작 인덱스, 끝 인덱스를 인자로 받고 마지막에 몇 번째 작은 원소를 찾을 것인지를 정해주는 인자 4개를 각각 정렬을 시작하는 함수에 넣고 동작을 시작한다. 첫번째 평균 선형시간 알고리즘은 말 그대로 평균적으로 선형시간이 걸리지만, 이 알고리즘의 경우 이미 정렬 되어있는 경우에도 모든 원소들을 비교하며 돌아야 하므로 O(nlogn)의 시간까지 걸릴 수 있다고 한다. 이를 해결하기 위해 최악의 경우에도 선형시간 탐색이 가능한 알고리즘을 고안해보았는데, 간단하게 말하면 피벗을 랜덤으로 잡는 알고리즘과 비슷했다. 자세한 부분은 코드를 참고하면서 설명하려고 한다.

 

[평균 선형시간 선택]

위의 코드는 평균 선형시간 선택 알고리즘의 main으로 실행되는 코드의 부분이다. 앞서 말했던 배열, 배열의 시작과 끝 그리고 target의 인덱스 값을 인자로 받는다.

 

먼저 start와 fin이 같다면 원소가 하나만 존재한다는 뜻이 되므로 탐색을 할 필요도 없이 바로 start인덱스 안에 있는 값을 반환하면 된다. 원소가 1개 이상이라면 원하는 target의 인덱스에 도달할 때까지 partition 함수를 진행하면서 리턴되는 인덱스가 target과 같아질 때까지 재귀 반복을 실행한다. 여기서 partition 함수의 동작을 살펴보기 위해 아래와 같은 코드를 첨부하였다.

 

Partition은 인자로 들어온 값의 범위를 대상으로 퀵소트와 같은 방식으로 정렬을 수행하는 방식이다. 하지만 퀵소트와 달리 완전히 정렬하는 것을 목표로 하는 것이 아니라, 피봇을 정해두고, 그 피봇을 기준으로 왼쪽은 작은 숫자를 오른쪽은 큰 숫자를 위치하게 하는 것이 목표이다.

 

그렇게 해서, 피봇이 몇 번째 인덱스에 해당하는지를 리턴하여 이 리턴된 인덱스가 target 인덱스보다 클 경우 왼쪽 즉 더 작은 쪽에서 범위에 해당하는 인덱스이므로 왼쪽을 탐색해야 할 것이고 반대로 작을 경우에는 오른쪽을 탐색하면 된다. 이러한 과정을 하기 위해서 첫번째 원소부터 탐색하기 위해 i는 -1부터 시작하고, j는 start 인덱스부터 시작하게 된다. J를 피봇과 비교하여 작으면 자리를 바꾸고 아니면 j의 인덱스를 증가시켜주는 방식을 반복하여 j가 인덱스의 마지막에 위치해 있을 경우 i에 위치한 원소보다 j가 작을 경우에는 피봇과 i인덱스의 수를 바꿔주는 것으로 왼쪽과 오른쪽에 피봇을 기준으로 정렬이 되게 된다. 이 과정을 원소 1개가 남을때까지 target을 찾을때까지반복하게 되면 결국 target인덱스에 있는 값을 얻을 수 있게 된다. 그 값이 target번째로 작은 원소의 값이 되는 것이다.

 

처음에, i=0, j=1의 인덱스 값을 주고 시작을 하였더니, 제일 첫 번째 원소를 검사하지 못해서 결과값이 이상하게 나오는 문제가 발생하였다. 이는 첫번째 인덱스까지 비교를 해 주니까 없어지는 문제였다. 또한, index를 초과해 버리는 문제가 발생하였는데, 마지막에 j인덱스(피봇)과 i인덱스를 비교하려고 하는데, 데이터는 100까지 즉 인덱스는 99까지인데 while문의 마지막에서 j가 ++을 해서 100의 값으로 끝나버리게 되므로 인덱스 초과 문제가 발생하게 되는 것이었다. 이를 막기 위해서 만약에 j의 값이 배열의 크기 값과 똑같다면 1을 빼주는 방식으로 문제를 해결하였다.

 

[최악 선형시간 선택]

반대로 최악의 경우에도 선형시간을 탐색하는 알고리즘 코드를 보면, 우선 데이터가 5개 이상인 경우에는 별도의 과정을 거칠 필요 없이 원하는 인덱스에서 값을 뽑아서 바로 리턴하는 코드를 추가하였다. 그 이외의 코드는 사실 전의 평균 선형시간 선택 코드와 다를바가 없어보인다. 앞서 말했듯이, 최악의 케이스 즉 이미 배열이 정렬되어있는데 하나씩 partition을 할 때 일어나는 문제를 해결하기 위해서는, 피봇을 항상 맨 마지막 숫자로만 설정을 하면 비효율적이기 때문에 아래와 같은 방법으로 피봇을 설정해주었다. 피봇을 설정해주는 함수는 findPivot으로 아래와 같다.

 

이 함수는 아래의 partition 함수에서 불려와서 쓰이는 함수로, pivot을 어떻게 설정할 것인지에 대해 정해주는 findPivot 함수이다. 이 함수의 동작을 살펴보면, 우선 배열의 범위의 마지막 fin값을 인자로 받는다. 이 fin값이 5의 배수인지 아닌지를 체크해서, 새로 만들어질 배열의 크기를 책정하는데, 이 배열은 범위 안에 있는 수들을 5개씩 묶어서 그룹을 만들고, 그 그룹 안의 중간값을 구하기 위해, 즉 그 그룹들의 중간값의 인덱스를 구하기 위해서 만든 배열이다. 그리고 이 배열의 중간값을 또 구해서, 이 인덱스에 있는 배열의 값을 구한 것이 피봇의 위치가 되는 것이다. 이것을 리턴해서, 원래 맨 마지막 수만 계속 피봇으로 설정했던 것과 달리 이러한 방법으로 피봇을 설정하면 worst case에도 대비할 수 있는 알고리즘이 나오게 된다.

 

위와 같이 리턴받은 값을 피봇의 인덱스로 정하고, 이 인덱스에 있는 값과 마지막에 있는 값을 바꾸어 피봇의 값이 중요한 것이니, 위치는 마지막에 있는 피봇으로 정하여 나머지 partition 동작을 수행한다. 이는 저번에 했던 랜덤 피봇의 퀵소트와 비슷한 양상을 볼 수 있었다.

 

[평균 선형시간 선택 결과]

이 알고리즘을 이용하여 원하는 수의 결과가 잘 나오는 것을 알 수 있었다. Index는 4999 즉 마지막 숫자 인덱스로 설정했기 때문에 맞는 결과가 나오는 것을 볼 수 있었다. 이외에 다른 숫자들도 돌려보았으나 맞는 정렬과 선택 결과가 나오는 것을 확인하였다. 숫자가 1부터 5000까지의 범위이므로, 인덱스+1을 한 결과값의 숫자가 나오는 것을 확인할 수 있다. 이번 보고서에는 따로 시간 측정을 하지 않아도 되기 때문에 시간 측정은 하지 않고 결과만을 출력해보았다. 이 시간 복잡도는 위에서 계속 언급했다싶히, 평균적으로 선형시간 O(n)의 시간복잡도를 가지고 있지만, 최악의 경우에는 더 걸릴 수 있는 알고리즘이다. 이 부분을 개선하기 위해 아래의 최악 선형시간 알고리즘을 구현한 것이다.

 

[최악 선형시간 선택 결과]

마찬가지로 원하는 선택 결과가 잘 나오는 것을 확인할 수 있다. 이것은 쳬계적으로 pivot을 구하여 정하고 연산하였기 때문에 어떠한 경우에도 선형시간을 가지는 알고리즘이다. 두 알고리즘을 구현하며 선형시간 선택 알고리즘의 구현 방법과 시간 복잡도를 알아보았다.