03 Modul Algoritma Pemrograman II Sorting

MODUL PERKULIAHAN
Algoritma dan
Pemrograman
II
Sorting
(masih dalam pengerjaan)
Fakultas Program Studi Tatap Muka Kode MK Disusun Oleh
Teknik Teknik Informatika 06210001 Esa Fauzi, S.T., M.T.
03
Abstract Kompetensi
Resume ringkas/singkat, akurat, dan Mahasiswa mampu
jelas terhadap isi materi pertemuan mengidentifikasikan berbagai masalah
mata kuliah mengacu pada apa yang dapat diselesaikan dengan
Rancangan Pembelajaran Semester teknik sorting serta dapat menggunakan
(RPS) dan menjelaskan berbagai macam teknik
sorting
Sorting
Sorting refers to arranging data in a particular format. Sorting algorithm specifies the
way to arrange data in a particular order. Most common orders are in numerical or
lexicographical order.
The importance of sorting lies in the fact that data searching can be optimized to a
very high level, if data is stored in a sorted manner. Sorting is also used to
represent data in more readable formats. Following are some of the examples of
sorting in real-life scenarios −
 Telephone Directory − The telephone directory stores the telephone
numbers of people sorted by their names, so that the names can be
searched easily.
 Dictionary − The dictionary stores words in an alphabetical order so that
searching of any word becomes easy.
In-place Sorting and Not-in-place Sorting

Sorting algorithms may require some extra space for comparison and temporary
storage of few data elements. These algorithms do not require any extra space and
sorting is said to happen in-place, or for example, within the array itself. This is
called in-place sorting. Bubble sort is an example of in-place sorting.
However, in some sorting algorithms, the program requires space which is more
than or equal to the elements being sorted. Sorting which uses equal or more space
is called not-in-place sorting. Merge-sort is an example of not-in-place sorting.
Stable and Not Stable Sorting

If a sorting algorithm, after sorting the contents, does not change the sequence of
similar content in which they appear, it is called stable sorting.
If a sorting algorithm, after sorting the contents, changes the sequence of similar
content in which they appear, it is called unstable sorting.
‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

2 Esa Fauzi, S.T., M.T. http://www.widyatama.ac.id
Stability of an algorithm matters when we wish to maintain the sequence of original
elements, like in a tuple for example.
Adaptive and Non-Adaptive Sorting Algorithm

A sorting algorithm is said to be adaptive, if it takes advantage of already 'sorted'
elements in the list that is to be sorted. That is, while sorting if the source list has
some element already sorted, adaptive algorithms will take this into account and will
try not to re-order them.
A non-adaptive algorithm is one which does not take into account the elements
which are already sorted. They try to force every single element to be re-ordered to
confirm their sortedness.
Important Terms
Some terms are generally coined while discussing sorting techniques, here is a brief
introduction to them −
Increasing Order
A sequence of values is said to be in increasing order, if the successive element is

greater than the previous one. For example, 1, 3, 4, 6, 8, 9 are in increasing order,
as every next element is greater than the previous element.
Decreasing Order
A sequence of values is said to be in decreasing order, if the successive element

is less than the current one. For example, 9, 8, 6, 4, 3, 1 are in decreasing order, as
every next element is less than the previous element.
Non-Increasing Order
A sequence of values is said to be in non-increasing order, if the successive

element is less than or equal to its previous element in the sequence. This order
occurs when the sequence contains duplicate values. For example, 9, 8, 6, 3, 3, 1

are in non-increasing order, as every next element is less than or equal to (in case
of 3) but not greater than any previous element.
Non-Decreasing Order
A sequence of values is said to be in non-decreasing order, if the successive

element is greater than or equal to its previous element in the sequence. This order
occurs when the sequence contains duplicate values. For example, 1, 3, 3, 6, 8, 9
are in non-decreasing order, as every next element is greater than or equal to (in
case of 3) but not less than the previous one.
Bubble Sort
Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-

based algorithm in which each pair of adjacent elements is compared and the
elements are swapped if they are not in order. This algorithm is not suitable for
large data sets as its average and worst case complexity are of Ο(n 2) where n is the
number of items.
How Bubble Sort Works?

We take an unsorted array for our example. Bubble sort takes Ο(n 2) time so we're
keeping it short and precise.
Bubble sort starts with very first two elements, comparing them to check which one
is greater.
In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we
compare 33 with 27.
We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −
Next we compare 33 and 35. We find that both are in already sorted positions.
Then we move to the next two values, 35 and 10.
We know then that 10 is smaller 35. Hence they are not sorted.
We swap these values. We find that we have reached the end of the array. After
one iteration, the array should look like this −
To be precise, we are now showing how an array should look like after each
iteration. After the second iteration, it should look like this −
Notice that after each iteration, at least one value moves at the end.
And when there's no swap required, bubble sorts learns that an array is completely
sorted.

Now we should look into some practical aspects of bubble sort.
Algorithm
We assume list is an array of n elements. We further assume that swap function
swaps the values of the given array elements.
begin BubbleSort(list)
for all elements of list

if list[i] > list[i+1]
swap(list[i], list[i+1])
end if
end for
return list
end BubbleSort
Pseudocode
We observe in algorithm that Bubble Sort compares each pair of array element
unless the whole array is completely sorted in an ascending order. This may cause
a few complexity issues like what if the array needs no more swapping as all the
elements are already ascending.
To ease-out the issue, we use one flag variable swapped which will help us see if
any swap has happened or not. If no swap has occurred, i.e. the array requires no
more processing to be sorted, it will come out of the loop.
Pseudocode of BubbleSort algorithm can be written as follows −
procedure bubbleSort( list : array of items )
loop = list.count;
for i = 0 to loop-1 do:

swapped = false
for j = 0 to loop-1 do:
/* compare the adjacent elements */

if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if
end for

/*if no number was swapped that means
array is sorted now, break the loop.*/
if(not swapped) then

break
end if
end for
end procedure return list

Implementation
One more issue we did not address in our original algorithm and its improvised
pseudocode, is that, after every iteration the highest values settles down at the end
of the array. Hence, the next iteration need not include already sorted elements. For
this purpose, in our implementation, we restrict the inner loop to avoid already
sorted values.
Implementation in C
Live Demo
#include <stdio.h>
#include <stdbool.h>
#define MAX 10
int list[MAX] = {1,8,4,6,0,3,5,2,7,9};
void display() {
int i;
printf("[");
// navigate through all items

for(i = 0; i < MAX; i++) {
printf("%d ",list[i]);
}
printf("]\n");
}
void bubbleSort() {
int temp;
int i,j;
bool swapped = false;
// loop through all numbers

for(i = 0; i < MAX-1; i++) {
swapped = false;

// loop through numbers falling ahead
for(j = 0; j < MAX-1-i; j++) {
printf(" Items compared: [ %d, %d ] ",
list[j],list[j+1]);
// check if next number is lesser than current no

// swap the numbers.
// (Bubble up the highest number)
if(list[j] > list[j+1]) {

temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
swapped = true;
printf(" => swapped [%d, %d]\n",list[j],list[j+1]);
} else {
printf(" => not swapped\n");
}
// if no number was swapped that means

// array is sorted now, break the loop.
if(!swapped) {
break;
}
printf("Iteration %d#: ",(i+1));

display();
}
void main() {
printf("Input Array: ");
display();
printf("\n");
bubbleSort();
printf("\nOutput Array: ");
display();
}
If we compile and run the above program, it will produce the following result −
Output
Input Array: [1 8 4 6 0 3 5 2 7 9 ]
Items compared: [ 1, 8 ] => not swapped
Items compared: [ 8, 4 ] => swapped [4, 8]

Iteration 1#: [1 4 6 0 3 5 2 7 8 9 ]
Iteration 2#: [1 4 0 3 5 2 6 7 8 9 ]
Iteration 3#: [1 0 3 4 2 5 6 7 8 9 ]
Iteration 4#: [0 1 3 2 4 5 6 7 8 9 ]
Iteration 5#: [0 1 2 3 4 5 6 7 8 9 ]
Output Array: [0 1 2 3 4 5 6 7 8 9 ]
Insertion Sort
This is an in-place comparison-based sorting algorithm. Here, a sub-list is

maintained which is always sorted. For example, the lower part of an array is
maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list,
has to find its appropriate place and then it has to be inserted there. Hence the
name, insertion sort.
The array is searched sequentially and unsorted items are moved and inserted into
the sorted sub-list (in the same array). This algorithm is not suitable for large data

sets as its average and worst case complexity are of Ο(n 2), where n is the number
of items.
How Insertion Sort Works?

We take an unsorted array for our example.
Insertion sort compares the first two elements.
It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted
sub-list.
Insertion sort moves ahead and compares 33 with 27.
And finds that 33 is not in the correct position.
It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we
see that the sorted sub-list has only one element 14, and 27 is greater than 14.
Hence, the sorted sub-list remains sorted after swapping.
By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.

These values are not in a sorted order.
So we swap them.
However, swapping makes 27 and 10 unsorted.
Hence, we swap them too.
Again we find 14 and 10 in an unsorted order.
We swap them again. By the end of third iteration, we have a sorted sub-list of 4
items.
This process goes on until all the unsorted values are covered in a sorted sub-list.
Now we shall see some programming aspects of insertion sort.

Algorithm
Now we have a bigger picture of how this sorting technique works, so we can derive
simple steps by which we can achieve insertion sort.
Step 1 − If it is the first element, it is already sorted. return
1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is
greater than the
value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until list is sorted
Pseudocode
procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */

valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] >

valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */

A[holePosition] = valueToInsert
end for
end procedure
Implementation in C
Live Demo
#include <stdio.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {

int i;
for(i = 0;i < count-1;i++) {

printf("=");
}
printf("=\n");
}
void display() {
int i;
printf("[");

for(i = 0;i < MAX;i++) {
printf("%d ",intArray[i]);
}
printf("]\n");
}
void insertionSort() {
int valueToInsert;
int holePosition;
int i;

for(i = 1; i < MAX; i++) {
// select a value to be inserted.

valueToInsert = intArray[i];
// select the hole position where number is to be inserted

holePosition = i;
// check if previous no. is larger than value to be

inserted
while (holePosition > 0 && intArray[holePosition-1] >
valueToInsert) {
intArray[holePosition] = intArray[holePosition-1];
holePosition--;
printf(" item moved : %d\n" , intArray[holePosition]);
}
if(holePosition != i) {
printf(" item inserted : %d, at position : %d\n" ,
valueToInsert,holePosition);
// insert the number at hole position
intArray[holePosition] = valueToInsert;
}
printf("Iteration %d#:",i);
display();

}
}
void main() {
display();
printline(50);
insertionSort();
printf("Output Array: ");
display();
printline(50);
}
Output
Input Array: [4 6 3 2 1 9 7 ]
==================================================
Iteration 1#:[4 6 3 2 1 9 7 ]
item moved : 6
item moved : 4
item inserted : 3, at position : 0
Iteration 2#:[3 4 6 2 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
Iteration 3#:[2 3 4 6 1 9 7 ]
item moved : 6
item moved : 4
item moved : 3
item moved : 2
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
item moved : 9
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================
Selection Sort
Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place

comparison-based algorithm in which the list is divided into two parts, the sorted
part at the left end and the unsorted part at the right end. Initially, the sorted part is
empty and the unsorted part is the entire list.
The smallest element is selected from the unsorted array and swapped with the
leftmost element, and that element becomes a part of the sorted array. This process
continues moving unsorted array boundary by one element to the right.

This algorithm is not suitable for large data sets as its average and worst case
complexities are of Ο(n2), where n is the number of items.
How Selection Sort Works?

Consider the following depicted array as an example.
For the first position in the sorted list, the whole list is scanned sequentially. The first
position where 14 is stored presently, we search the whole list and find that 10 is
the lowest value.
So we replace 14 with 10. After one iteration 10, which happens to be the minimum
value in the list, appears in the first position of the sorted list.
For the second position, where 33 is residing, we start scanning the rest of the list in
a linear manner.
We find that 14 is the second lowest value in the list and it should appear at the
second place. We swap these values.
After two iterations, two least values are positioned at the beginning in a sorted
manner.

The same process is applied to the rest of the items in the array.
Following is a pictorial depiction of the entire sorting process −

Now, let us learn some programming aspects of selection sort.
Algorithm
Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted
Pseudocode
procedure selection sort
list : array of items
n : size of list
for i = 1 to n - 1
/* set current element as minimum*/
min = i
/* check the element to be minimum */
for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for
/* swap the minimum element with the current element*/

if indexMin != i then
swap list[min] and list[i]
end if
end for
end procedure
Implementation in C
Live Demo
#include <stdio.h>
#define MAX 7
int intArray[MAX] = {4,6,3,2,1,9,7};
void printline(int count) {

int i;
for(i = 0;i < count-1;i++) {

printf("=");
}
printf("=\n");

}
void display() {
int i;
printf("[");

for(i = 0;i < MAX;i++) {
printf("%d ", intArray[i]);
}
printf("]\n");
}
void selectionSort() {
int indexMin,i,j;

for(i = 0; i < MAX-1; i++) {
// set current element as minimum

indexMin = i;
// check the element to be minimum

for(j = i+1;j < MAX;j++) {
if(intArray[j] < intArray[indexMin]) {
indexMin = j;
}
}
if(indexMin != i) {
printf("Items swapped: [ %d, %d ]\n" , intArray[i],
intArray[indexMin]);
// swap the numbers

int temp = intArray[indexMin];
intArray[indexMin] = intArray[i];
intArray[i] = temp;
}
printf("Iteration %d#:",(i+1));
display();
}
}
void main() {
display();
printline(50);
selectionSort();
printf("Output Array: ");
display();
printline(50);
}

Output
Input Array: [4 6 3 2 1 9 7 ]
==================================================
Items swapped: [ 4, 1 ]
Iteration 1#:[1 6 3 2 4 9 7 ]
Iteration 2#:[1 2 3 6 4 9 7 ]
Iteration 3#:[1 2 3 6 4 9 7 ]
Iteration 4#:[1 2 3 4 6 9 7 ]
Iteration 5#:[1 2 3 4 6 9 7 ]
Iteration 6#:[1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================


03 Modul Algoritma Pemrograman II Sorting

Uploaded by

Copyright:

Available Formats

03 Modul Algoritma Pemrograman II Sorting

Uploaded by

Document Information

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

03 Modul Algoritma Pemrograman II Sorting

Uploaded by

Copyright:

Available Formats

MODUL PERKULIAHAN

In-place Sorting and Not-in-place Sorting

Stable and Not Stable Sorting

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

Adaptive and Non-Adaptive Sorting Algorithm

A sequence of values is said to be in increasing order, if the successive element is

A sequence of values is said to be in decreasing order, if the successive element

A sequence of values is said to be in non-increasing order, if the successive

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

A sequence of values is said to be in non-decreasing order, if the successive

Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-

How Bubble Sort Works?

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

Then we move to the next two values, 35 and 10.

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

for all elements of list

for i = 0 to loop-1 do:

for j = 0 to loop-1 do:

/* compare the adjacent elements */

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

if(not swapped) then

end procedure return list

int list[MAX] = {1,8,4,6,0,3,5,2,7,9};

// navigate through all items

bool swapped = false;

// loop through all numbers

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

// check if next number is lesser than current no

if(list[j] > list[j+1]) {

// if no number was swapped that means

printf("Iteration %d#: ",(i+1));

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

This is an in-place comparison-based sorting algorithm. Here, a sub-list is

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

How Insertion Sort Works?

Insertion sort compares the first two elements.

Insertion sort moves ahead and compares 33 with 27.

And finds that 33 is not in the correct position.

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

However, swapping makes 27 and 10 unsorted.

Hence, we swap them too.

Again we find 14 and 10 in an unsorted order.

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

for i = 1 to length(A) inclusive do:

/* select value to be inserted */

/*locate hole position for the element to be inserted */

while holePosition > 0 and A[holePosition-1] >

/* insert the number at hole position */

int intArray[MAX] = {4,6,3,2,1,9,7};

void printline(int count) {

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

for(i = 0;i < count-1;i++) {

// navigate through all items

// loop through all numbers

// select a value to be inserted.

// select the hole position where number is to be inserted

// check if previous no. is larger than value to be

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place

‘20 Algoritma & Pemrograman II Biro Akademik dan Pembelajaran

/locate hole position for the element to be inserted /