Sorted List

SortedList 

장점 : 원하는 원소를 빠르게 찾을 수 있다.

단점 : 새로운 아이템을 넣을 때 들어갈 자리를 찾아야한다.

 

Unsorted List에서 정보를 어떻게 저장할 것인가만 달라진다. Insert, Delete 함수만 바꿔보자.

+ RetrieveItem을 좀 더 효율적으로 만들어보자.

 

InsertItem(ItemType newItem)

현재 위치 표시할 location, 끝까지 검사하기 위한 moreToSearch.

newItem이랑 리스트 원소 비교했을 때 Less( newItem이 더 작으면) location 앞에 넣는다.

Greater(newItem이 더 크면) newItem보다 큰 원소가 나올 때까지 위치를 뒤로 옮긴다.

location이 확정되면, location보다 뒤에 있는 원소들을 한 칸씩 뒤로 밀어주고 그 자리에 insert한다. &  length+1

 

location 확정 후 원소들을 한 칸씩 뒤로 밀 때, 반드시 맨 뒤 원소부터 옮겨야한다. location 다음 칸부터 옮기면 원래 그 자리에 있던 원소 잃어버림.

void SortedType::InsertItem(ItemType newItem){
	int location = 0;
    bool moreToSearch = (location < length);
   	
    while(moreToSearch){
    	switch(newItem.ComparedTo(info[location])){
        	case Less:
            	moreToSearch = false;
            	break;
            case Equal:
            	break;
            case Greater:
            	location++;
                moreToSearch = location < length;
                break;
            }
        for(int index = length; index > location; index--){
        	info[index] = info[index-1];
            }
        info[location] = newItem;
        length++;
    }

 

 

DeleteItem(ItemType item)

삭제할 아이템이 리스트 어디에 있는지 찾아야한다.

리스트 원소가 삭제할 아이템이 아니면 다음 칸을 검사한다. (location+1)

삭제할 위치가 확정되었으면 다음 칸 원소들을 한 칸씩 앞으로 땡겨준다. & length -1

이 때 location 바로 다음 칸부터 하나씩 옮겨줘야한다. 맨 뒤에서부터 옮기면 값 잃어버림.

void SortedType::DeleteItem(ItemType item){
	int location = 0;
    
    while(item.ComparedTo(info[location]) != Equal){
    	location++;
        }
    
    for(int index = location +1; index < location; index--){
    	info[index-1] = info[index];
        }
    length--;
    }

 

RetrieveItem(ItemType& item, bool found)

unsorted List에서는 item이 있는지 확인하기 위해 모든 원소를 검사해야했다.

sortedList에서는 Binary Search를 이용하자!

중간 인덱스를 만들어서 item과 info[midPoint] 값을 비교한다. item이 더 작으면 앞 쪽 절반만 다시 보자 (last = midPoint -1)

item이 더 크면 뒤 쪽 절반만 다시 보자. (first = midPoint +1).

계속 절반을 자르면서 보다가 first > last인 순간 끝난다. 

void SortedType::RetrieveItem(ItemType& item, bool found){
	int midPoint;
    int first = 0;
    int last = length-1;
    bool moreToSearch = (first <= last);
    found = false;
    
    while(!found && moreToSearch){
    	int midPoint = (first+last)/2;
        switch(item.ComparedTo(info[midPoint])){
        	case Less:
            	last = midPoint -1;
                moreToSearch = (first <= last);
                break;
            case Equal:
            	found = true;
                item = info[midPoint];
                break;
            case Greater:
            	first = midPoint +1;
                moreToSearch = (first <= last);
                break;
            }
        }
    }

binarySearch

 

 

UnsortedList와 SortedList 시간복잡도