Unsorted array list에 이어 오늘은 Sorted array list에 대해 알아보겠습니다.
(클래스, 배열에 대한 기초지식이 필요합니다. 관련 지식이 없으신 분들께서는 먼저 클래스와 배열에 대한 정보를 접하고 오셔야합니다.)
SortedList란? 요소들을 특정 기준으로 정렬해서 나열하는 데이터 구조입니다. 동일한 요소의 데이터들을 추가하고 제거하고 수정하고 조회하고 비우고 등의 작동 메커니즘이 SortedList라는 틀을 통해 이뤄진다고 생각하시면 됩니다. 정렬이 되어있는 형태이기 때문에 특정 데이터를 조회할 때 Unsorted list에 비해 더욱 빠른 검색이 가능하다는 장점이 있습니다.
SortedList의 Class
member variable(멤버변수): length(UnsortedList에 들어있는 데이터의 갯수), Item[](데이터가 저장될 배열), CurrentPosition(특정 배열 칸에 접근하기 위한 index)
member function(멤버함수): Add(추가), Delete(삭제), MakeEmpty(비우기), IsFull(꽉 찼는지 여부), LengthIs(들어온 데이터 갯수), RetrieveItem(특정 데이터 찾기), ResetList(index를 -1로 초기화), GetNextItem(index에 +1 연산)
다음은 SortedList의 각 멤버함수 별 설명입니다. SortedList를 크기5짜리 배열로 묘사하고 설명을 진행한 점 참고해주세요. (RetrieveItem에서는 10짜리 배열로 묘사)
Add(UnsortedList에 데이터를 추가한다)
그림1에 ‘3’을 넣으면
그림2처럼 SortedList 맨 앞 공간인 [0]에 ‘3’이 삽입 된 것을 알 수 있습니다. 여기까지는 UnsortedList와 똑같지만 차이는 지금부터 생깁니다. SortedList가 오름차순 정렬을 따른다고 가정해보겠습니다. 다음 데이터로 ‘2’를 SortedList에 삽입한다고 했을 때 정렬 기준에 따라 ‘2’, ‘3’으로 나열 되어야하지만 현재 3의 앞 공간에 자리가 없습니다. 그렇다면 자리가 생겨야겠죠.
그림3을 보면 ‘2’가 맨 앞에 올 수 있도록 ‘3’을 [1]로 움직였고
그림4처럼 빈공간이 된 [0]에 ‘2’가 삽입된 것을 확인할 수 있습니다. 그렇다면 그림4 상태에서 추가로 ‘1’을 삽입한다고 하면 어떨까요?
오름차순이기 때문에 ‘1’, ‘2’, ‘3’순으로 나열이 되야합니다. 그러려면 [0]에 자리가 생겨야하고 그걸 위해 그림5처럼 제일 뒤쪽에 위치한 ‘3’을 먼저 한 칸 옮기고
그 후에 그림6처럼 ‘2’또한 한 칸 뒤로 옮겼습니다. 이제 SortedList 내에 제일 작은 수가 될 ‘1’을 위한 자리가 마련 되었고
[0]에 ‘1’이 삽입에 성공했습니다. 이처럼 SortedList의 Add는 새로운 데이터가 삽입될 때 정렬기준으로 그 데이터가 저장 될 위치가 결정이 되고 그에 따라 나머지 기존의 데이터들이 재정렬됩니다.
Delete(SortedList의 데이터를 삭제한다)
그렇다면 SortedList에서 데이터를 삭제를 한다면 어떤 방식으로 나열이 이뤄질까요?
다섯 개의 데이터로 채워진 SortedList에서 ‘3’을 삭제 해보겠습니다.
그림9처럼 데이터 사이의 빈공간이 있는 상태로 배열을 내버려둬서는 안됩니다. UnsortedList에서도 말했었지만 리스트는 선형관계가 특징이기 때문입니다.
그림10을 보니 방금 공부한 Add쪽과 비슷한 과정이 연상되지 않으시나요? Add에서는 빈공간을 만들기 위해 한 칸씩 뒤로 옮겼었다면 이번에는 빈공간을 채우기 위해서 빈공간 직후의 공간에서부터 한 칸씩 옮겨와야합니다. 그 일환으로 [3]에 있던 ‘4’를 [2]로 옮겨왔습니다.
이번엔 [4]에 있던 ‘5’를 [3]으로 옮겨왔습니다. Add와 마찬가지로 Delete또한 데이터의 삭제 이후에 기존의 데이터들은 정렬기준에 맞게 재정렬 되야합니다.
MakeEmpty(SortedList의 데이터를 모두 제거한다)
MakeEmpty 함수를 수행하면 이름처럼 SortedList내의 모든 데이터가 삭제됩니다.
LengthIs(SortedList에 속한 데이터의 갯수를 파악한다)
LengthIs 멤버함수는 현재 SortedList안에 데이터가 얼마나 들어왔는지 파악할 수 있는 함수입니다.
예를들면 그림14 상태의 SortedList에서 LengthIs를 수행하면 5를 반환하고
그림15 상태에서 LengthIs를 수행하면 3을 반환합니다.
IsFull(SortedList에 남은 자리가 있는지 파악한다.)
IsFull 멤버함수는 현재 SortedListd안에 데이터가 꽉 찼는지의 여부를 검사해주는 함수입니다.
예를들어 그림16 상태의 SortedList에서 IsFull 함수를 수행하면 True를 반환하고
그림17 상태에서 수행하면 False를 반환할 것입니다.
RetrieveItem(SortedList에서 특정 데이터를 검색한다)
RetrieveItem 멤버함수는 이름처럼 SortedList내에서 특정 item을 검색하는 함수입니다.
SortedList는 데이터 요소들이 특정 기준(여기서는 오름차순)으로 정렬이 되어있기 때문에 조금 특별한 방법으로 데이터를 검색합니다. 바로 BinarySearch입니다. 만약 SortedList 내에서 ‘4’를 찾는다고 한다면 우리의 눈은 ‘[3]에 있네’라고 생각하겠지만 SortedList는 그렇게 하지못합니다. 그러면 이제부터 SortedList가 어떻게 ‘4’를 찾는지 설명해보겠습니다.
그림19를 보시면 [0], [4], [9]에 각각 First, Mid, Last라는 변수가 생긴 것을 확인할 수 있습니다. BinarySearch를 도와주는 변수라고 생각하면 편합니다. First는 제일 처음의 위치 값으로 초기화하고 Last는 제일 마지막 위치 값으로 초기화합니다. SortedList의 length는 ‘10’이지만 여기서는 index값이 기준이 되기 때문에 Last를 9로 초기화 했습니다. 그리고 Mid는 First와 Last를 더하고 2로 나눈 값으로 초기화합니다. 소수점까지 ‘4.5’로 값이 나오지만 소수점 아래는 버리고 ‘4’로 초기화 해주었습니다.그렇다면 First, Mid, Last 이 세 개의 변수로 어떻게 ‘4’를 찾을 수 있을까요? 우리가 찾는 ‘4’는 그림19에서 Mid(=[4])에 위치한 값(‘5’)보다 작습니다. 그렇다는 것은 정렬된 SortedList 내에서 Mid를 포함한 오른쪽 영역은 우리가 찾는 ‘4’가 없다는 것을 의미합니다.
그렇기 때문에 그림20처럼 빨간색으로 처리하였습니다. 이 다음 과정은 First, Mid, Last의 값 갱신입니다. Mid포함 오른 쪽은 더이상 신경쓰지 않아도 되는 값이기 때문에 우리가 신경써야 할 범위에서 제일 마지막은 Mid-1이 됩니다. 그래서 Last는 [3]으로 갱신되는 것이죠. First는 우리가 신경써야 할 범위에서 제일 작기 때문에 그대로 놔둬도 되고 Mid는 다시 First와 Last를 합하여 2로 나눈 값으로 갱신됩니다. ‘1.5’에서 소숫점 아래는 버린 ‘1’로 갱신 되는 것이죠. ‘4’는 그림20에서 Mid(=[1])에 위치한 값(‘2’)보다 큽니다. 그렇다는 것은 정렬된 SortedList 내에서 Mid를 포함한 왼쪽 영역은 ‘4’가 없다는 것을 의미합니다.
그렇기 때문에 그림21처럼 빨간색으로 처리하였습니다. 다시 First, Mid, Last의 값을 갱신해야겠죠? Mid포함 왼쪽은 더이상 신경쓰지 않아도 되는 값이기 때문에 우리가 신경써야 할 범위에서 제일 처음은 Mid+1이 됩니다. 그래서 First는 [2]로 갱신되는 것이죠. Last는 우리가 신경써야 할 범위에서 제일 크기 때문에 그대로 놔둬도 되고 Mid는 다시 First와 Last를 합하여 2로 나눈 값으로 갱신됩니다. ‘2.5’에서 소숫점 아래는 버린 ‘2’로 갱신 되는 것이죠. ‘4’는 그림21에서 Mid(=[2])에 위치한 값(‘3’)보다 큽니다. 그렇다는 것은 정렬된 SortedList 내에서 Mid를 포함한 왼쪽 영역은 ‘4’가 없다는 것을 의미합니다.
그렇기 때문에 그림22처럼 빨간색으로 처리하였습니다. 다시 First, Mid, Last의 값을 갱신해야겠죠? Mid포함 왼쪽은 더이상 신경쓰지 않아도 되는 값이기 때문에 우리가 신경써야 할 범위에서 제일 처음은 Mid+1이 됩니다. 그래서 First는 [3]로 갱신되는 것이죠. Last는 우리가 신경써야 할 범위에서 제일 크기 때문에 그대로 놔둬도 되고 Mid는 다시 First와 Last를 합하여 2로 나눈 값으로 갱신됩니다. ‘3’으로 갱신 되는 것이죠.
그런데 그림22를 보시면 더 이상 흰색 영역은 [3]부분 밖에 없습니다. 그리고 ‘4’는 [3]에 위치한 값과 동일합니다. 즉, SortedList에서 [3]에 우리가 찾던 ‘4’가 있다는 것을 발견한 것입니다. 이 방법으로 데이터를 찾는 것은 SortedList에 데이터가 많이 삽입되어 있을수록 진가를 발휘합니다. 하지만 명심하셔야합니다. 이 방법은 정렬이 되어있어야만 사용이 가능하다는 것을 말이죠.
이번 글에서는 배열 리스트에서 SortedList를 다뤄보았는데요, UnsortedList와 마찬가지로 구현이 쉬운 편에 속하지만 그래도 Add, Delete를 할 때마다 재정렬이 필요하고 RetrieveItem에서는 꽤 복잡해보이는 BinarySearch를 사용해야 하기 때문에 어렵다고 느껴질 수도 있습니다. 하지만 데이터 검색을 할 때 Sorted list의 복잡도는 O(logN), Unsorted list의 복잡도는 O(N)이기 때문에 N이 커질수록 검색효율에서 기하급수적인 차이가 발생할 것이고 그렇게 되면 재정렬과 BinarySearch 구현에 들어가는 노력은 감수할만 하다고 생각됩니다.
혹시 글에서 주제와 관련되어 오류가 있는 내용이 있다면 댓글로 피드백 부탁드리겠습니다. 글 보러 와주신 모든 분들 정말 감사합니다.
