특정 위치의 값 찾기

배열의 Data를 정렬시켰을 때 n번째 위치의 값을 찾는 알고리즘 입니다.

 

해당 알고리즘은 Quick_Sort알고리즘에서 활용했던 Partition을 재활용합니다 :)

teus-kiwiee.tistory.com/8

Quick Sort

탐색 방법 살펴보면..

1. partition을 진행

2. partition 후 바꿀 위치와 내가 찾는 n번째 위치가 동일한지 비교한다.

 == > 같으면 pivot 원소를 반환 후 종료

3. 왼쪽과 오른쪽 부분배열에 대해서 1~2반복

 

결국 Quick Sort알고리즘을 활용한 탐색알고리즘의 일종입니다.

다른점 이라면, pivot원소의 이동이 발생하지 않고 빠르게 값만 찾아줍니다.

 

import random
#Generate ordered List
Data = [i for i in range(1000)]
#Shuffle ordered list
random.shuffle(Data)

#Index Search에 사용할 partition 함수를 정의
def partition(DT_list_part, Max):
    #partition을 진행할 pivot 원소를 선택합니다.
    pivot = DT_list_part[0]
    left = 1
    right = Max-1
    #pivot 원소를 옮기기 위해서, 사전에 pivot원소를 제외한 부분배열을
    #1차적으로 정렬해줍니다(Pivot 원소 기준으로 왼쪽은 작게, 오른쪽은 크게)
    while left<=right:        
        if DT_list_part[left]<pivot and DT_list_part[right]>pivot:
            left = left+1
            right = right-1
        elif DT_list_part[left]>pivot and DT_list_part[right]>pivot:
            right = right-1
        elif DT_list_part[left]<pivot and DT_list_part[right]<pivot:
            left = left+1
        elif DT_list_part[left]>pivot and DT_list_part[right]<pivot:
            temp = DT_list_part[left]
            DT_list_part[left] = DT_list_part[right]
            DT_list_part[right] = temp
    #Pivot 원소가 이동한 Index를 반환해줍니다.
    return right
        

def find_special_index_value(DT_list, find_index):    
    n = len(DT_list)    
    #Pivot 원소가 이동할 수 있는 Index를 반환합니다.
    change_loc = partition(DT_list, n)   
    #만약 Pivot원소가 이동할 Index가 원하는 Index라면 알고리즘 종료 후 해당 value값 반환
    if change_loc == find_index:        
        return DT_list[0]        
    #Pivot의 이동 Index가 찾는 Index랑 다르면
    #이제 Pivot 원소를 제외한 나머지 배열을 부분배열로 나누고
    #find_index와 change_loc을 비교해서 왼쪽 or 오른쪽 한쪽의 부분배열에서
    #알고리즘을 반복해서 진행합니다.
    #Index를 찾을경우 Pivot원소의 value를 반환하기 때문에
    #해당 원소값을 find_value에 저장하고, 이 값을 알고리즘의 결과물로 반환합니다.
    elif change_loc >= find_index:
        find_value = find_special_index_value(DT_list[1:change_loc+1], find_index)
    elif change_loc < find_index:        
        find_value = find_special_index_value(DT_list[change_loc+1:], find_index-(change_loc+1))        
    return find_value

    
loc = find_special_index_value(Data, 7)