Sorted list and Unsorted list
Linear relationship: Each element except the first has a unique predecessor, and each element except sthe last has a unique successor
Unsorted list A list in which data items are placed in no particular order; the only relationship between data elements is the list predecessor and successor relationships.
Sorted list A list that is sorted by the value in the key; there is a semantic relationship among the keys of the items in the list.
Key The attributes that are used to determine the logical order of the list.
Unsorted list는 순서 없이 element들이 list안에 들어있다.
Sorted list는 key에 의해서 element들이 정렬되어있다.
ADT Unsorted list Operations
class constructor
class constructor는 object가 정의될 때 암묵적으로 호출되는 special member function이다.
값을 return할 수 없으며 여러개가 존재할 수 있고 컴파일러가 parameter에 따라서 맞는 constructor를 선택해서 실행한다. parameter가 없는 constructor는 default constructor이다.
item을 넣을때 length위치에 들어가며 length는 1증가한다.
RetrieveItem은 location이 length보다 작을 동안 루프를 돌며 item을 찾고 찾으면 found = true;
GetNextItem은 다음 item을 가져오는 method로 현재 위치에서 1을 더한 위치의 값을 item에 할당함.
element를 넣거나 삭제할때마다 length를 늘리고 줄인다.
deleteItem을 수행할때 중간에 있는 item을 삭제하면 뒤에 있는 요소들을 앞으로 한칸씩 당겨야하는데 연산이 많아지므로 unsorted의 특성을 활용해서 삭제할 위치에 마지막 요소의 값을 넣고 마지막 요소를 삭제하면 된다.
void UnsortedType::RetrieveItem(ItemType &item, bool &found)
// Pre: Key member of item is initialized.
// Post: If found, item’s key matches an element’s key in the list
// and a copy of that element has been stored in item;
// otherwise, item is unchanged.
{
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::GetNextItem(ItemType &item)
// Pre: List has been initialized. Current position is defined.
// Element at current position is not last in list.
// Post: Current position is updated to next position.
// item is a copy of element at current position.
{
currentPos++;
item = info[currentPos];
}
void UnsortedType::DeleteItem(ItemType item)
// Pre: item’s key has been inititalized.
// An element in the list has a key that matches item’s.
// Post: No element in the list has a key that matches item’s.
{
int location = 0;
while (item.ComparedTo(info[location]) != EQUAL)
location++;
// move last element into position where item was located
info[location] = info[length - 1];
length--;
}
C++
복사
ItemType class정의
const int MAX_ITEM = 5;
enum RelationType { LESS, EQUAL, GREATER };
class ItemType // declares class data type
{
public:
void void // 3 public member functions
RelationType ComparedTo(ItemType) const;
Print() const;
Initialize(int number);
private:
int value; // 1 private data member
// could be any different type
};
C++
복사
ItemType class 구현
#include “itemtype.h”
#include <iostream>
RelationType ItemType::ComparedTo(ItemType otherItem) const {
if (value < otherItem.value)
return LESS;
else if (value > otherItem.value)
return GREATER;
else
return EQUAL;
}
void ItemType::Print() const {
using namespace std;
cout << value << endl;
}
void ItemType::Initialize(int number) { value = number; }
C++
복사
enum은 개발자가 봤을 때 한눈에 이해할 수 있도록 값을 모아놓은것이지만 실제로는 integer로 동작하며 아무런 제약이 없어서 에러를 발생시키지 않아서 예상치 않게 동작할 수 있기 때문에 enumeration class를 사용하는것이 좋다.
SortedType
UnsortedType과 다르게 method실행 후에도 sorted상태를 유지하기 위해서 변경해야하는 method는 InsertItem과 DeleteItem이다.
UnsortedType에서는 가장 뒤에 삽입하면 됐지만 SortedType에서는 InsertItem은 적합한 위치를 찾아서 삽입할 때 뒤의 요소들을 전부 한칸씩 뒤로 밀어야 하는데 데이터가 손실되는것을 막기 위해서 뒤에 있는 item부터 한칸씩 이동해서 공간을 확보하고 deleteItem에서는 삭제한 요소의 바로 다음 요소부터 앞으로 한칸씩 이동하면 된다.
void SortedType ::InsertItem(ItemType item) {
bool moreToSearch;
int location = 0;
// find proper location for new element
moreToSearch = (location < length);
while (moreToSearch) {
switch (item.ComparedTo(info[location])) {
case LESS:
moreToSearch = false;
break;
case GREATER:
location++;
moreToSearch = (location < length);
break;
}
} // make room for new element in sorted list
for (int index = length; index > location; index--)
info[index] = info[index - 1];
info[location] = item;
length++;
}
void SortedType ::DeleteItem(ItemType item) {
int location = 0;
// find location of element to be deleted
while (item.ComparedTo(info[location]) != EQUAL)
location++;
// move up elements that follow deleted item in sorted list
for (int index = location + 1; index < length; index++)
info[index - 1] = info[index];
length--;
}
C++
복사
binary search in a sorted List
RetrieveItem method의 성능을 향상시키기 위해서 이진탐색을 활용할 수 있다.
데이터가 정렬되어있을때 원하는 아이템을 찾으려면 중간부터 보면 된다.
void SortedType::RetrieveItem(ItemType &item, bool &found)
// ASSUMES info ARRAY SORTED IN ASCENDING ORDER
{
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;
}
}
}
C++
복사
big-O notation
worst case를 가정하고 계산한다.
N²을 넘어가면 알고리즘 성능이 좋지 않다고 보고 N²까지를 polynomial time이라고 한다.
