[삽입정렬 예제]
/*
Insertion Sort Example
삽입 정렬 예시
*/
#include <iostream>
using namespace std;
/*
Insertion into a sorted list
*/
template <class T>
void Insert(const T &e, T *a, int i)
{
a[0] = e;
while (e < a[i])
{
a[i + 1] = a[i];
i--;
}
a[i + 1] = e;
}
/*
Insertion Sort
*/
template <class T>
void InsertionSort(T *a, const int n)
{
for (int j = 2; j < n; j++)
{
T temp = a[j];
Insert(temp, a, j - 1);
}
}
int main(void)
{
//책의 간단한 예시를 참고한 코드
int arr[6] = { 0 }; //0번째 인덱스는 사용하지 않는다
cout << "기존 배열: ";
for (int i = 1; i <= 5; i++)
{
arr[i] = 6 - i;
cout << arr[i] << " ";
}
cout << endl;
InsertionSort(arr, sizeof(arr) / sizeof(int));
cout << "정렬된 배열: ";
for (int i = 1; i <= 5; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
[Exercises 2]
/*
Write a C++ function that implements Binary Insertion Sort
이진 삽입 정렬을 구현하는 C++ 함수를 작성한다
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
template <typename T>
T binarySearch(T *a, int data, int left, int right)
{
if (right <= left) //찾지 못했을 경우
if (data > a[left])
return left + 1;
else
return left;
int mid = (left + right) / 2;
if (data > a[mid])
return binarySearch(a, data, mid + 1, right);
else if (data == a[mid])
return mid + 1;
else
return binarySearch(a, data, left, mid - 1);
}
//예시에서 정의한 삽입정렬과 구조는 동일하다
template <typename T>
void insertionSort(T *a, const int n)
{
for (int i = 1; i < n; i++)
{
int j = i - 1;
int temp = a[i];
int index = binarySearch(a, temp, 0, j);
while (j >= index)
{
a[j + 1] = a[j];
j--;
}
a[j + 1] = temp;
}
}
int main(void)
{
int *arr;
int length;
srand((unsigned)time(NULL));
cout << "배열의 길이는 >";
cin >> length;
arr = new int[length];
cout << "정렬 전 배열: ";
for (int i = 0; i < length; i++)
{
arr[i] = rand() % 200;
cout << arr[i] << " ";
}
cout << endl;
cout << "정렬 후 배열: ";
insertionSort(arr, length);
for (int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}
[Exercises 3]
/*
Write a C++ function that implements Linked Insertion Sort
링크드 리스트 삽입 정렬을 구현하는 C++ 함수를 작성한다
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
template <typename T>
class Node
{
private:
T data;
Node *next;
Node *first;
public:
Node(T d = 0) :data(d), next(NULL)
{
first = NULL;
}
void push(T d) //앞에 삽입
{
Node *temp = new Node(d);
temp->next = first;
first = temp;
}
Node *Insert(Node *newNode) //InsertionSort에 필요한 함수
{
if (first == NULL || first->data >= newNode->data) //리스트가 비어있거나 first의 data가 새로운 노드의 data보다 큰 경우
{
newNode->next = first;
first = newNode;
return first;
}
Node *current = first;
Node *previous = NULL;
while (current != NULL&& current->data < newNode->data) //current의 data가 newNode의 data보다 클때까지
{
previous= current;
current = current->next;
}
newNode->next = current;
previous->next = newNode;
return first;
}
void insertionSort()
{
Node *current = first->next; //first의 다음 노드를 임시로 저장하고
first->next = NULL; //first의 다음 노드를 비운다
while (current)
{
Node *temp = current;
current = current->next;
first = Insert(temp);
}
}
void display()
{
Node *current = first;
while (current)
{
cout << current->data << "->";
current = current->next;
}
cout << endl;
}
};
int main(void)
{
Node<int> intList;
srand((unsigned)time(NULL));
for (int i = 0; i < 10; i++)
intList.push(rand() % 100 + 1);
intList.display();
intList.insertionSort();
intList.display();
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.