Lab6 - DataStructures

Mapúa Institute of Technology
School of EECE
Department of Computer Engineering
LAB 6 – Sorting Algorithms

COE116L (Data Structures)
DPadilla School of EECE

JCuesta Mapúa Institute of Technology
Lab 6 - Sorting Algorithms Data Structures
Page 2 of 19 Lab Manual
Lab 6 – Visual Studio 2005 Fundamentals

Sorting Algorithms
6.1 OBJECTIVES
At the end of this laboratory, you should be able to:
1. Write and implement selection sort

2. Write and implement insertion sort
3. Write and implement merge sort
4. Write and implement quick sort
5. Write and implement bubble sort
6. Compare sorting algorithms
6.2 INTRODUCTION
Sorting Algorithms
Selection Sort
Selection sort is one of the O(n2) sorting algorithms, which makes it quite inefficient for sorting
large data volumes. Selection sort is notable for its programming simplicity and it can over perform
other sorts in certain situations.
Algorithm
The idea of algorithm is quite simple. Array is imaginary divided into two parts - sorted
one and unsorted one. At the beginning, sorted part is empty, while unsorted
one contains whole array. At every step, algorithm finds minimal element in the unsorted
part and adds it to the end of the sorted one. When unsorted part becomes empty,
algorithmstops.
When algorithm sorts an array, it swaps first element of unsorted part with minimal element and
then it is included to the sorted part. This implementation of selection sort in not stable. In case
of linked list is sorted, and, instead of swaps, minimal element is linked to the unsorted part,
selection sort is stable.
Insertion Sort
Although it is one of the elementary sorting algorithms with O(n2) worst-case time, insertion sort is
the algorithm of choice either when the data is nearly sorted (because it is adaptive) or when the
problem size is small (because it has low overhead).
For these reasons, and because it is also stable, insertion sort is often used as the recursive base
case (when the problem size is small) for higher overhead divide-and-conquer sorting algorithms,
such as merge sort or quick sort.

Algorithm
Insertion sort algorithm somewhat resembles selection sort. Array is imaginary divided into two
parts - sorted one andunsorted one. At the beginning, sorted part contains first element of the
array and unsorted one contains the rest. At every step, algorithm takes first element in
the unsorted part and inserts it to the right place of the sorted one. Whenunsorted
part becomes empty, algorithm stops.
Quicksort
Quicksort is a fast sorting algorithm, which is used not only for educational purposes, but widely
applied in practice. On the average, it has O(n log n) complexity, making quicksort suitable for
sorting big data volumes. The idea of the algorithm is quite simple and once you realize it, you can
write quicksort as fast as bubble sort.
Algorithm
The divide-and-conquer strategy is used in quicksort. Below the recursion step is described:
1. Choose a pivot value. We take the value of the middle element as pivot value, but it can be
any value, which is in range of sorted values, even if it doesn't present in the array.
2. Partition. Rearrange elements in such a way, that all elements which are lesser than the
pivot go to the left part of the array and all elements greater than the pivot, go to the right
part of the array. Values equal to the pivot can stay in any part of the array. Notice, that
array may be divided in non-equal parts.
3. Sort both parts. Apply quicksort algorithm recursively to the left and the right
parts.
Bubble Sort
Bubble sort is a simple and well-known sorting algorithm. It is used in practice once in a blue moon
and its main application is to make an introduction to the sorting algorithms. Bubble sort belongs to
O(n2) sorting algorithms, which makes it quite inefficient for sorting large data volumes. Bubble sort
is stable and adaptive.
Algorithm
1. Compare each pair of adjacent elements from the beginning of an array and, if they are in
reversed order, swap them.
2. If at least one swap has been done, repeat step 1.
You can imagine that on every step big bubbles float to the surface and stay there. At the step,
when no bubble moves, sorting stops.
Merge Sort
Algorithm
Assume, that both arrays are sorted in ascending order and we want resulting array to maintain
the same order. Algorithm to merge two arrays A[0..m-1] and B[0..n-1] into an array C[0..m+n-

1] is as following:
1. Introduce read-indices i, j to traverse arrays A and B, accordingly. Introduce write-index k to

store position of the first free cell in the resulting array. By default i = j = k = 0.
2. At each step: if both indices are in range (i < m and j < n), choose minimum of (A[i],
B[j]) and write it toC[k]. Otherwise go to step 4.
3. Increase k and index of the array, algorithm located minimal value at, by one. Repeat step
2.
4. Copy the rest values from the array, which index is still in range, to the resulting array.
6.3 LAB EXERCISES
Sample Programs
A. Selection Sort
Instructions: Create a new project (Lab6) in the same solution (e.g. Mapua.DataStruct) you created
in the previous lab. Name the source file SelectionSort-ArrayBasedList.cpp. See example full path
below:
Z:\Mapua.DataStruct\Lab6\SelectionSort-ArrayBasedList.cpp
Note: Remember to make this project the Startup project.
Program Listing 6.1 - SelectionSort-ArrayBasedList.cpp

1. // Name:
2. // Group No./Members:
3. // Course & Section:
4. // Filename: SelectionSort-ArrayBasedList.cpp
5. // Description:
6.
7. #include<iostream>
8. #include<cassert>
9. using namespace std;
10.
11. template<class elemType>
12. Aclass ArrayListType
13. A{
14. Apublic:
15. A
16. A void SelectionSort();
17. A void Insert(const elemType&);
18. A //Use to search the list for a given item;
19. A int SeqSearch(const elemType&) const;
20. A //constructor
21. A ArrayListType(int size=0);

22. A //Overload the assignment operator

23. A const ArrayListType<elemType>& operator = (const
24. AArrayListType<elemType>&);
25. A
26. A //destructor
27. A ~ArrayListType() { delete[] list;}
28. A
29. void PrintList();
30.
31. Aprivate:
32. A int MinLocation(int, int);
33. A void Swap(int, int);
34. A
35. A int maxSize;
36. A int length; //length of the list
37. A elemType *list;
38. A};
39. A
40. A//Constructor definition
41. Atemplate<class elemType>
42. AArrayListType<elemType>::ArrayListType(int size) {
43. A if(size <= 0)
44. A {
45. A cerr<<"The array must be positive";
46. A cerr<<"\ncreating an array of size 100"<<endl;
47. A maxSize = 100;
48. A }
49. A else maxSize = size;
50. A length = 0;
51. A list = new elemType[maxSize];
52. A assert(list !=NULL);
53. A}
54. A//Overloaded assigment operator
56. Aconst ArrayListType<elemType>& ArrayListType<elemType>::operator=
57. A (const ArrayListType<elemType>& otherList)
58. A{
59. A if(this != &otherList) //avoid self-assignment
60. A {
61. A delete[] list;
62. A maxSize= otherList.maxSize;
63. A length = otherList.length;
64. A
65. A list = new elemType[maxSize]; //create the array
66. A assert(list !=NULL); //if unable to allocate memory
67. A //space, terminate program
68. A for(int i=0; i<length; i++)
69. A list[i] = otherList.list[i];
70. A }
71. A return *this;

72. A
73. A}
74. A
75. A
77. Avoid ArrayListType<elemType>::PrintList(){
78. A for(int i=0; i<length; ++i)
79. A {
80. A cout<<list[i]<<" ";
81. A }
82. A cout<<"\n";
83. A //list = NULL; //to avoid HEAP corruption
84. A
85. A}
86. A
88. Aint ArrayListType<elemType>::SeqSearch(const elemType &item) const{
89. A int loc;
90. A bool found = false;
91. A for(loc = 0; loc <length; loc++)
92. A if (list[loc] == item)
93. A {
94. A found =true;
95. A break;
96. A }
97. A if(found) return loc;
98. A else return -1;
99. A}
100. A
102. Avoid ArrayListType<elemType>::Insert(const elemType& item)
103. A{
104. A int loc;
105. A if(length ==0) //list is empty
106. A list[length++] = item;
107. A else if(length==maxSize)
108. A cerr<<"Cannot insert in a full list."<<endl;
109. A else
110. A {
111. A loc = SeqSearch(item);
112. A if (loc == -1)
113. A list[length++] = item;
114. A else
115. A cerr<<"the item to be inserted is already in"
116. A <<"the list. No duplication is allowed."<<endl;
117. A }
118. A}
119. A
120. A// MinLocation - function that returns the index
121. A// of the smallest element

122. Atemplate <class elemType>

123. Aint ArrayListType<elemType>::MinLocation(int first, int last)
124. A{
125. A int minIndex; //
126. A minIndex = first;
127. A
128. A for(int loc = first+1; loc <= last; loc++)
129. A {
130. A if(list[loc] < list[minIndex])
131. A minIndex = loc;
132. A }
133. A return minIndex;
134. A}
135. A
137. Avoid ArrayListType<elemType>::Swap(int first, int second)
138. A{
139. A elemType temp;
140. A temp = list[first];
141. A
142. A list[first] = list[second];
143. A list[second] = temp;
144. A}
145. A
147. Avoid ArrayListType<elemType>::SelectionSort()
148. A{
149. A int minIndex;
150. A for(int loc = 0; loc < length-1; loc++)
151. A {
152. A minIndex = MinLocation(loc, length-1);
153. A Swap(loc,minIndex);
154. A }
155. A
156. A}
157. A
158. Aint main()
159. A{
160. A ArrayListType<char> alphabet;
161. A char letter;
162. A cout<<"\nEnter uppercase letters\n"
163. A <<"(End lowercase to terminate) >> ";
164. A cin>>letter;
165. A while(letter >= 'A' && letter <= 'Z')
166. A {
167. A alphabet.Insert(letter);
168. A cin>>letter;
169. A }
170. A cout<<"The list before using selection sort: "<<endl;
171. A alphabet.PrintList();

172. A
173. A alphabet.SelectionSort();
174. A cout<<"The list before using selection sort: "<<endl;
175. a alphabet.PrintList();
176. a
177. a
178. a system("pause");
179. a return 0;
180. A}
Instructions: Build the project. Run the program and use the inputs shown in Figure 6.1
Figure 6.1 – Sample Run (SelectionSort-ArrayBasedList.cpp)
B. Insertion Sort
Instructions: Add the source file shown in Program Listings 6.2.A, 6.2.B, 6.2.C, 6.2.D,
and 6.2.E. Remember to exclude the previous file. Name the files as QueueClass.h. ,
QueueClass.cpp, and Lab4-Sample04(ArrayImplementation).cpp respectively. Build the
file and trace the program execution.
Program Listing 6.2.A - LinkedListType.h

1. // Name:
4. // Filename: LinkedListType.h
5. // Description:
6.
7. #ifndef LinkedListType_h

8. #define LinkedListType_h
9.
10. //Node definition
11.
12. template<class Type>
13. struct nodeType
14. {
15. Type info;
16. nodeType<Type> * link;
17. A};
18. A
19. Atemplate<class Type>
20. Aclass LinkedListIterator
21. A{
22. Apublic:
23. A LinkedListIterator(); //default constructor
24. A
25. A LinkedListIterator(nodeType<Type> *ptr); //constructor with 1
26. Aparameter
27. A
28. A Type operator*(); //overload the dereference operator
29. A LinkedListIterator<Type> operator++(); //overload the preincrement
30. Aoperator
31. A
32. A bool operator==(const LinkedListIterator<Type>& right) const;
33. A//overload the equality operator
34.
35. private:
36. A nodeType<Type> * current; //pointer to point to the current node in
37. Athe linked list
38. A};
39. A
41. Aclass LinkedListType
42. A{
43. Apublic:
44. A //Overload the assignment operator
45. A const LinkedListType<Type>& operator = (const
46. ALinkedListType<Type>&);
47. A void InitializeList();
48. A bool IsEmptyList() const;
49. A void Print() const;
50. A int Length() const;
51. A void DestroyList();
52. A
53. A Type front() const;
54. A Type back() const;
55. A
56. A virtual bool Search(const Type& searchItem) const = 0;
57. A virtual void InsertFirst(const Type& newItem) = 0;

58. A virtual void InsertLast(const Type& newItem) = 0;

59. A virtual void DeleteNode(const Type& deleteItem) = 0;
60. A
61. A LinkedListIterator<Type> begin();
62. A LinkedListIterator<Type> end();
63. A
64. A LinkedListType(); //default constructor
65. A LinkedListType(const LinkedListType<Type>& otherList); //copy
66. Aconstructor
67. A ~LinkedListType(); //destructor
68. Aprotected:
69. A int count;
70. A nodeType<Type> *first;
71. A nodeType<Type> *last;
72. Aprivate:
73. A void CopyList(const LinkedListType<Type>& otherList);
74. A};
75. A
76. A#include "LinkedListType.cpp"
77. #endif
Program Listing 6.2.B - LinkedListType.cpp

1. // Name:
4. // Filename: LinkedListType.cpp
5. // Description:
6.
7. #ifndef LinkedListType_cpp
8. #define LinkedListType_cpp
9. #include <stdio.h>
10. #include "LinkedListType.h"
11.
12. //LinkedListType function definitions
13. template <class Type>
14. bool LinkedListType<Type>::IsEmptyList() const
15. {
16. A return (first ==NULL);
17. A}
18. A
19. Atemplate <class Type>
20. Avoid LinkedListType<Type>::DestroyList()
21. A{
22. A nodeType<Type> *temp;
23. A while(first !=NULL)
24. A {
25. A temp = first;

26. A first = first->link;

27. A delete temp;
28. A }
29. A last = NULL;
30. A count = 0;
31. A}
32. A
34. void LinkedListType<Type>::Print() const
35. A{
36. A nodeType<Type> *current;
37. A current = first;
38. while(current !=NULL)
39. A {
40. A cout<<current->info<<" ";
41. A current = current->link;
42. A }
43. A}
44. A
46. ALinkedListType<Type>::LinkedListType(const LinkedListType<Type>
47. A&otherList)
48. A{
49. A first = NULL;
50. A CopyList(otherList);
51. A}
52. A
53. A//default constructor
55. ALinkedListType<Type>::LinkedListType()
56. A{
57. A first = NULL;
58. A last = NULL;
59. A count =0;
60. A
61. A}
62. A
63. A//destructor
65. ALinkedListType<Type>::~LinkedListType()
66. A{
67. A DestroyList();
68. A}
69. A
70. A
71. A//LinkedListIterator function definitions
73. ALinkedListIterator<Type>::LinkedListIterator()
74. A{
75. A current = NULL;

76. A}
77. A
79. ALinkedListIterator<Type>::LinkedListIterator(nodeType<Type> *ptr)
80. A{
81. A current = ptr;
82. A}
83. A
85. AType LinkedListIterator<Type>::operator*()
86. A{
87. A return current->info;
88. A}
89. A
91. ALinkedListIterator<Type> LinkedListIterator<Type>::operator++()
92. A{
94. A return *this;
95. A}
96. A
97. A template <class Type>
98. Abool LinkedListIterator<Type>::operator==(const LinkedListIterator<Type>&
99. Aright) const
100.{ A
101. Areturn (current != right.current);
102.} A
103. A
104.#endifA
Program Listing 6.2.C – UnOrderedLinkedList.h

1. // Name:
4. // Filename: UnOrderedLinkedList.h
5. // Description:
6.
7. #ifndef UnOrderedLinkedList_h
8. #define UnOrderedLinkedList_h
10.
11. template <class Type>
12. class UnorderedLinkedList:public LinkedListType<Type>
13. {
14. public:
15. A bool Search(const Type& searchItem) const;

16. A void InsertFirst(const Type& newItem);

17. A void InsertLast(const Type& newItem);
18. A void DeleteNode(const Type& deleteItem);
19. A
20. A void LinkedInsertionSort();
21. A};
22. A
23. A#include "UnOrderedLinkedList.cpp"
24. #endif
Program Listing 6.2.D – UnOrderedLinkedList.cpp

1. // Name:
4. // Filename: UnOrderedLinkedList.cpp
5. // Description:
6.
7. #ifndef UnOrderedLinkedList_cpp
8. #define UnOrderedLinkedList_cpp
9. #include "UnOrderedLinkedList.h"
11.
13. Abool UnorderedLinkedList<Type>::Search(const Type& searchItem) const
14. A{
15. A nodeType<Type> *current; //pointer to traverse the list
16. A bool found = false;
17. A
18. A current = first; //set current to point to the first node in the
19. Alist
20. A while(current !=NULL && !found)
21. A if(current ->info == searchItem)
22. A found = true;
23. A else
25. A return found;
26. A}
27. A
29. Avoid UnorderedLinkedList<elemType>::LinkedInsertionSort()
30. A{
31. A nodeType<elemType> *lastInOrder;
32. A nodeType<elemType> *firstOutOfOrder;
33. A nodeType<elemType> *current;
34. A nodeType<elemType> *trailCurrent;
35. A

36. A lastInOrder = first;

37. A if(first == NULL)
38. A cerr<<"Cannot sort an empty list."<<endl;
39. A else if (first->link ==NULL)
40. A cerr<<"It is already in order."<<endl;
41. A else
42. A while(lastInOrder->link != NULL)
43. A {
44. A firstOutOfOrder = lastInOrder->link;
45. A if(firstOutOfOrder->info < first->info)
46. A {
47. A lastInOrder->link = firstOutOfOrder->link;
48. A firstOutOfOrder ->link = first;
49. A first = firstOutOfOrder;
50. A }
51. A else
52. A {
53. A trailCurrent = first;
54. A current = first->link;
55. A while(current->info < firstOutOfOrder->info)
56. A {
57. A trailCurrent = current;
59. A }
60. A if(current != firstOutOfOrder)
61. A {
62. A lastInOrder->link = firstOutOfOrder->link;
63. A firstOutOfOrder->link = current;
64. A trailCurrent->link = firstOutOfOrder;
65. A }
66. A else
67. A lastInOrder = lastInOrder->link;
68. A }
69. A }
70. A}
71. A
73. Avoid UnorderedLinkedList<Type>::InsertFirst(const Type& newItem)
74. A{
75. A nodeType<Type> *newNode;
76. A
77. A newNode = new nodeType<Type>;
78. A newNode-> info = newItem;
79. A newNode->link = first;
80. A first = newNode;
81. A count++;
82. A if(last == NULL)
83. A last = newNode;
84. A
85. A}

86. A
88. Avoid UnorderedLinkedList<Type>::InsertLast(const Type& newItem)
89. A{
90. A nodeType<Type> *newNode;//pointer to create the new node;
91. A newNode = new nodeType<Type>;
92. A newNode->info = newItem;
93. A newNode->link = NULL;
94. A
95. A if(first==NULL)
96. A {
97. A first = newNode;
98. A last = newNode;
99. a count++;
100. a}
101. aelse
102. a{
103. a last->link = newNode;
104. a last = newNode;
105. a count++;
106. a}
107.} a
108. a
109.template<class
a Type>
110.void UnorderedLinkedList<Type>::DeleteNode(const
a Type& deleteItem)
111.{ a
112. anodeType<Type> *current ;
113. anodeType<Type> *trailCurrent;
114. abool found;
115. a
116. aif(first==NULL)
117. a cout<<"Cannot delete from an empty list"<<endl;
118. aelse
119. a{
120. a if(first->info == deleteItem)
121. a {
122. a current = first;
123. a first = first->link;
124. a count--;
125. a
126. a if(first ==NULL)
127. a last = NULL;
128. a delete current;
129. a }
130. a else
131. a {
132. a found = false;
133. a trailCurrent = first;
134. a current=first->link;
135. a

136. a while(current != NULL && !found)

137. a {
138. a if (current ->info !=deleteItem)
139. a {
140. a trailCurrent = current;
141. a current = current->link;
142. a }
143. a else
144. a found = true;
145. a }
146. a if(found)
147. a {
148. a trailCurrent->link = current->link;
149. a count--;
150. a if(last == current)
151. a last = trailCurrent;
152. a delete current;
153. a }
154. a else
155. a cout<<"The item to be deleted is not in the
156.list"<<endl;
a
157. a }
158. a}
159.} a
160. a
161.#endifa
162. a
Program Listing 6.2.E – ProgramEntryPoint.cpp

1.// Name:
4. // Filename: ProgramEntryPoint.cpp
5. // Description:
6.
7. #include "UnOrderedLinkedList.h"
8. #include <iostream>
9.
10. using namespace std;
11. int main()
12. {
13. A cout<<"Insertion Sort"<<endl;
14. A UnorderedLinkedList<int> list1;
15. A
16. A int number;

17. A cout<<"Enter numbers end with -1 >> ";

18. A cin>>number;
19. A //list1.InsertFirst(number);
20. A while(number != -1)
21. A {
22. A list1.InsertLast(number);
23. A cin>>number;
24. A
25. A
26. A }
27. A cout<<"The list before using insertion sort: "<<endl;
28. A list1.Print();
29. A
30. A list1.LinkedInsertionSort();
31. A cout<<"The list after using insertion sort: "<<endl;
32. A list1.Print();
33. A return 0;
34. A}
35.

6.4 QUESTIONS
1. Assume the following keys: 7, 28, 31, 40, 5, 20

The first four keys are in order. To move 5 to its proper position using insertion sort, exactly
how many key comparisons are executed?
2. Both mergesort and quicksort sort a list by partitioning the list. Explain how mergesort
differs from quicksort in partitioning the list.

6.5 PROGRAMMING EXERCISES
1. Revise ProgramEntryPoint.cpp to include a function named Search to determine whether

the item to be added is already in the list.
Filenames:
Entry Point: Lab6-ProgExer01-Entry.cpp
Copy the other .h and .cpp files used in Program Listings 6.2.A to 6.2.D in your
Project.
2. Make a Linked-List version of Program Listing 6.1.
Filenames:
Class Definition: Lab6-ProgExer02.h
Class Implementation: Lab6-ProgExer03.cpp
3. Write a C++ program that implements quicksort algorithm. Assume the following list of
keys: 16, 38, 54, 80, 22, 65, 55, 48, 64, 95, 5, 100, 58, 25, 36. Use pivot as the middle
element of the list. Display the resulting list after one call to the partition procedure and the
resulting list after two calls to the partition procedure.
Filenames:
4. Write a program to test mergesort for linked lists.

5. Write a program to test bubble sort for linked lists.
Filenames:


Lab6 - DataStructures

Uploaded by

Copyright:

Available Formats

Lab6 - DataStructures

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lab6 - DataStructures

Uploaded by

Copyright:

Available Formats

Mapúa Institute of Technology

LAB 6 – Sorting Algorithms

DPadilla School of EECE

Lab 6 – Visual Studio 2005 Fundamentals

At the end of this laboratory, you should be able to:

1. Write and implement selection sort

DPadilla School of EECE

DPadilla School of EECE

1. Introduce read-indices i, j to traverse arrays A and B, accordingly. Introduce write-index k to

6.3 LAB EXERCISES

Note: Remember to make this project the Startup project.

Program Listing 6.1 - SelectionSort-ArrayBasedList.cpp

DPadilla School of EECE

22. A //Overload the assignment operator

DPadilla School of EECE

DPadilla School of EECE

122. Atemplate <class elemType>

DPadilla School of EECE

Figure 6.1 – Sample Run (SelectionSort-ArrayBasedList.cpp)

Program Listing 6.2.A - LinkedListType.h

DPadilla School of EECE

DPadilla School of EECE

58. A virtual void InsertLast(const Type& newItem) = 0;

Program Listing 6.2.B - LinkedListType.cpp

DPadilla School of EECE

26. A first = first->link;

DPadilla School of EECE

Program Listing 6.2.C – UnOrderedLinkedList.h

DPadilla School of EECE

16. A void InsertFirst(const Type& newItem);

Program Listing 6.2.D – UnOrderedLinkedList.cpp

DPadilla School of EECE

36. A lastInOrder = first;

DPadilla School of EECE

DPadilla School of EECE

136. a while(current != NULL && !found)

Program Listing 6.2.E – ProgramEntryPoint.cpp

DPadilla School of EECE

17. A cout<<"Enter numbers end with -1 >> ";

DPadilla School of EECE

1. Assume the following keys: 7, 28, 31, 40, 5, 20

DPadilla School of EECE

6.5 PROGRAMMING EXERCISES

1. Revise ProgramEntryPoint.cpp to include a function named Search to determine whether

4. Write a program to test mergesort for linked lists.

DPadilla School of EECE

You might also like