자료구조 - Unsorted List and Sorted List
list는 data와 data사이의 linear relationship이 존재햐야 한다.
linear relationship은 Base address에 있는 element를 제외하고는 전부 다 유일한 전임자(predecessor)가 존재해야 하고 제일 마지막 원소를 제외하고는 모두 유일한 후임자(successor)가 존재해야 한다.
list의 종류는 Unsorted List와 Sorted List 두 가지가 있는데 Sorted List는 임의의 원소를 뽑았을 때 그 원소의 앞 또는 뒤에 있는 원소와 모종의 정렬 관계가 있는 것을 의미한다.
이때 리스트를 정렬을 결정하는 요소를 key라고 한다.
Unsorted List의 헤더를 다음과 같이 짜볼 수 있다.
class UnsortedType {
int length;
ItemType info[MAX_ITEMS];
int currentPos;
public:
UnsortedType();
void InsertItem(ItemType item);
void DeleteItem(ItemType item);
bool IsFull() const;
int LengthIs() const;
void RetrieveItem(const ItemType& item, bool& found);
void ResetList();
void GetNextItem(ItemType& item);
};
여기서 InsertItem, DeleteItem는 Transformer에 해당하는 부분으로 각각 원소를 삽입하거나 제거하는 과정을 수행한다.
IsFull, LengthIs, RetrieveItem는 Observers로 각각 리스트가 전부 찼는지, 리스트의 길이는 얼마인지 그리고 특정 원소가 존재하는지 확인한다.
마지막으로 ResetList, GetNextItem는 Iterators로 리스트를 초기화하거나 리스트의 다음 값으로 이동한다.
이제 Unsorted List를 실제로 구현해보면 다음과 같이 짤 수 있다.
#include "unsorted.h"
UnsortedType::UnsortedType() {
length = 0;
}
void UnsortedType::InsertItem(ItemType item) {
info[length] = item;
length++;
}
void UnsortedType::DeleteItem(ItemType item) {
int location = 0;
for (location; location < length; location++) {
if (item.ComparedTo(info[location]) == EQUAL) {
info[location] = info[length - 1];
length--;
}
}
}
bool UnsortedType::IsFull() const {
return (length == MAX_ITEMS);
}
int UnsortedType::LengthIs() const {
return length;
}
void UnsortedType::RetrieveItem(const ItemType& item, bool& found) {
bool moreToSearch;
int location = 0;
found = false;
moreToSearch = (location < length);
while (moreToSearch && !found) {
switch (item.ComparedTo(info[location])) {
case LESS:
case GREATER: location++;
moreToSearch = (location < length);
break;
case EQUAL: found = true;
item = info[location];
break;
}
}
}
void UnsortedType::ResetList() {
currentPos = -1;
}
void UnsortedType::GetNextItem(ItemType& item) {
currentPos++;
item = info[currentPos];
}
InsertItem을 하게 되면 현재 length의 위치에 item을 삽입하게 되고 list의 총 길이가 길어졌으므로 length++로 늘린다.
DeleteItem은 list의 앞에서부터 순서대로 탐색하면서 해당 원소가 나올때 까지 찾고 만약 해당 원소를 찾게되면 정렬되지 않은 리스트이기 때문에 가장 마지막에 있는 원소를 해당 위치에 대입을 하고 마지막 원소를 지워주는 방식으로 delete를 수행한다.
RetrieveItem은 우리가 찾는 원소가 현재 위치의 값보다 작거나 크면 현재 위치를 다음으로 이동시켜 다음 위치의 값과 비교하고 현재 위치의 값고 찾는 원소가 같으면 찾았다고 하는 함수이다.
ResetList는 currentPos를 -1로 하여 현재 list를 초기화 해준다.
ComparedTo는 내부가 어떻게 생겼는지 알아야 비교할 수 있으므로 ItemType안에 존재한다.
ItemType은 다음과 같이 만들면 된다.
const int MAX_ITEMS = 100;
enum RelationType { LESS, GREATER, EQUAL };
class ItemType {
int value;
public:
ItemType();
RelationType ComparedTo(ItemType) const;
void Print(std::ostream&) const;
void Initialize(int number);
};
ItemType::ItemType() {
value = 0;
}
RelationType ItemType::ComparedTo(ItemType otherItem) const {
if (value < otherItem.value)
return LESS;
else if (value > otherItem.value)
return GREATER;
else
return EQUAL;
}
void ItemType::Initialize(int number) {
value = number;
}
void ItemType::Print(std::ostream& out) const {
out << value;
}
List의 최대 원소의 개수를 100개로 잡았고 비교를 할 때 파악하기 쉽게 하기 위해 enum을 사용해 LESS, GREATER, EQUAL를 비교하였다.
이제 Sorted List를 보면 Unsorted와 다른 모든것이 동일하지만 InsertItem과 DeleteItem부분만 다르게 수정해주면 된다.
그리고 RetrieveItem의 경우도 순서대로 정렬되어 있으므로 일일히 찾는 방법보다는 이분법으로 찾는 것이 시간 복잡도에서 더 유리하기 때문에 바꿔주면 된다.
void SortedType::InsertItem(ItemType item) {
bool moreToSearch;
int location = 0;
moreToSearch = (location < length);
while (moreToSearch) {
switch (item.ComparedTo(info[location])) {
case LESS: moreToSearch = false;
break;
case GREATER: location++;
moreToSearch = (location < length);
break;
}
}
for (int index = length; index > location; index--)
info[index] = info[index - 1];
info[location] = item;
length++;
}
void SortedType::DeleteItem(ItemType item) {
int location = 0;
while (item.ComparedTo(info[location]) != EQUAL)
location++;
for (int index = location + 1; index < length; index++)
info[index - 1] = info[index];
length--;
}
void SortedType::RetrieveItem(const ItemType& item, bool& found) {
int midPoint;
int first = 0;
int last = length - 1;
bool moreToSearch = (first <= last);
found = false;
while (moreToSearch && !found) {
midPoint = (first + last) / 2;
switch (item.ComparedTo(info[midPoint])) {
case LESS: last = midPoint - 1;
moreToSearch = (first <= last);
break;
case GREATER: first = midPoint + 1;
moreToSearch = (first <= last);
break;
case EQUAL: found = true;
item = info[midPoint];
break;
}
}
}
InsertItem을 하게 되면 먼저 0번째 원소부터 순서대로 원소를 비교하면서 우리가 삽입할 원소의 위치를 찾고, 해당 위치를 찾으면 제일 마지막 원소부터 한칸 씩 뒤로 밀어서 해당 위치에 우리가 삽입할 원소를 대입하면 된다.
DeleteItem은 list의 앞에서부터 순서대로 탐색하면서 해당 원소가 나올때 까지 찾고 만약 해당 원소를 찾게되면 해당 위치부터 뒤에있는 원소를 하나씩 당기고 전체 length의 수를 줄여서 리스트를 만든다.
RetrieveItem은 이분탐색을 이용하였는데 제일 앞의 index와 마지막의 index를 통해 중간의 위치에서의 값을 구하고 만약 중간 값이 찾는 값보다 큰 경우 중간 위치를 last로 하고 다시 중간 인덱스를 구하고 반대의 경우는 중간 위치를 first로 하여 다시 중간 인덱스를 구하는 방식으로 찾는다.
이렇게 이분탐색으로 원소를 찾을 경우 시간 복잡도는 $O(N)$에서 $O(\log_2 N)$로 감소하게 된다.
Python으로 Unsorted List를 구현하면 다음과 같이 구할 수 있다.
C++과의 차이점은 python의 경우 array의 크기를 미리 정해주지 않아도 되기 때문에 배열의 최대 원소의 개수가 정해져 있다면 해당하는 숫자보다 더 많은 원소가 들어갔는지 비교하는 과정이 따로 필요하다.
MAX_ITEMS = 100
class UnsortedType:
def __init__(self):
self.length = 0
self.info = []
self.current_pos = -1
def make_empty(self):
self.length = 0
def length_is(self):
return self.length
def is_full(self):
if self.length == MAX_ITEMS:
return True
return False
def insert_item(self, item):
self.info.append(item)
self.length += 1
def retrieve_item(self, item):
location = 0
while location < self.length:
if item.compared_to(self.info[location]) != Compare.EQUAL:
location += 1
else:
return True
return False
def delete_item(self, item):
location = 0
while item.compared_to(self.info[location]) != Compare.EQUAL:
location += 1
self.info[location] = self.info[self.length - 1]
self.length -= 1
def reset_list(self):
self.current_pos = -1
def get_next_item(self):
self.current_pos += 1
return self.info[self.current_pos]
def __str__(self):
self.reset_list()
print_list = []
for i in range(self.length):
print_list.append(str(self.get_next_item()))
return str(" ".join(print_list))
동일한 방법으로 Sortred List를 python으로 구현하면 다음과 같이 구할 수 있다.
class Compare(Enum):
LESS = 0
GREATER = 1
EQUAL = 2
class SortedType:
def __init__(self):
self.length = 0
self.info = []
self.current_pos = -1
def make_empty(self):
self.length = 0
def length_is(self):
return self.length
def is_full(self):
if self.length == MAX_ITEMS:
return True
return False
def insert_item(self, item):
self.info.append(item)
location = 0
while location < self.length:
if item.compared_to(self.info[location]) == Compare.LESS:
break
elif item.compared_to(self.info[location]) == Compare.GREATER:
location += 1
index = int(self.length)
while index > location:
self.info[index] = self.info[index - 1]
index -= 1
self.info[location] = item
self.length += 1
def retrieve_item(self, item):
first = 0
last = self.length - 1
while first <= last:
midpoint = int((first + last) / 2)
if item.compared_to(self.info[midpoint]) == Compare.EQUAL:
return True
elif item.compared_to(self.info[midpoint]) == Compare.LESS:
last = midpoint - 1
else:
first = midpoint + 1
return False
def delete_item(self, item):
location = 0
while item.compared_to(self.info[location]) != Compare.EQUAL:
location += 1
index = location + 1
while index < self.length:
self.info[index-1] = self.info[index]
index += 1
self.length -= 1
def reset_list(self):
self.current_pos = -1
def get_next_item(self):
self.current_pos += 1
return self.info[self.current_pos]
def __str__(self):
self.reset_list()
print_list = []
for i in range(self.length):
print_list.append(str(self.get_next_item()))
return str(" ".join(print_list))