By: Ziham Zawawi Mazlan
Sorting is an everyday activity in which the efficiency of the algorithm used is very important. There are many sorting algorithms designed for use on computers, and there are computer packages available that enable us to compare the merits of the merits of the various algorithms.
In many situations, we want to sort some 'things' into a certain order. We might want to put books or CDs into alphabetical order, or we may be using a packing algorithm that requires the data to be pre-sorted. With a small amount of data, this is easy to do by sight. For larger amounts of data we need the help of clearly defined algorithms.
So, now we will discuss about sorting using interchange sort algorithm and bubble sort algorithm. From these types of sorting, we will give explanation about these types deeply and discuss how we went to sort the pupils of 4 Pintar.
From the name list that we take, we must sort it using two way of sorting which is interchange sort algorithm and bubble sort algorithm. Sorting name is actually for us easily to see the list whether it is ascending or descending.
This is the name list of 4 Pintar pupils from Sekolah Kebangsaan Taman Kota Jaya, Kota Tinggi, Johor. There are 22 pupils in this class and the name list is not yet arranges according alphabetical order from A to Z. So, now we will sort the name list using two ways which are bubble sort algorithm and interchange sort algorithm.
No. NAME
1 Ahmad Johari Bin Yazid
2 Muhammad Syazwani Bin Abdul Wahab
3 Muhammad Nor Islam Bin Hussin
4 Aini Nazira Binti Shamsul
5 Kahirul Hamizan Bin Abdul Halim
6 Muhammad Qiyyam Bin Mohd Noor
7 Mohd Fikri Bin Mohd Idris
8 Emirul Iqbal Irman Fitri Bin Sulaiman
9 Anisa RAmadhany Binti Basrizal
10 Mohd Afiq Haikal Bin Mohd Lusli
11 Muhamad Firdaus Bin Ishak
12 Muhammad Haris Bin Azman
13 Luqman Hakimi Bin Armani
14 Nur Farahana Binti Jamain
15 Nurul Fatihah Binti Kamalrudin
16 Muhammad Ariffin Bin Abdul Rahman
17 Nurul Farahin Binti Azli
18 Muhammad Caniel Bin Rihaizan
19 Muhd Haziq Hamdani Bin Abd Jabar
20 Nur Syaidatul Alia Binti Rithaudeen
21 Wan Azizul Hazairie Bin Azizul
22 Muhammad Hazim Bin Azanam
Interchange Sort Algorithm
What is interchange sort algorithm? Interchange sort algorithm is one of the types of sorting data. In this method, we find the smallest number in the list or set is found and interchange it with the number in the first position. Then we find the second smallest number excluding the first is found, and swap it with the number in the second position. This process continues until list is sorted.
In example, we get the following (numbers in italics have been verified to be in the correct position by the algorithm):
Pass Order
0 7 5 2 4 10 1
1 1 5 2 4 10 7
2 1 2 5 4 10 7
3 1 2 4 5 10 7
4 1 2 4 5 10 7
5 1 2 4 5 7 10
Number of comparisons: 0 + 1 + 2 + 3 + 4 + 5 = 15 comparisons.
This example requires 15 comparisons to sort six numbers.
There are a few things to notice here. Firstly, the fourth pass did not change the order of the data - it merely checked that 5 were in the correct position. Secondly, the final pass verifies the position of two numbers - if the
second largest number has been put in the correct position, the largest must also be in the correct position. Because of this, we know that a set of m numbers will need m -1 passes to be put in the correct order.
The comparisons we are making between pairs of numbers are, in a sense, hidden in this algorithm. In each pass we need to find the smallest number of the remaining (unsorted) set3. This will need m - n comparisons on the nth pass, hence the total number of comparisons needed will be:
(m -1) + (m -2) + … + (m -[m -2]) + (m -[m -1]) = (m -1) + (m -2) + … + 2 + 1
= ½(m×(m -1))
So for our six-item example, this gives:
½(m×(m -1)) = ½(6×5)
= ½×30
= 15
If we had twice as much data (that is, 12 items) we would have:
½(m×(m -1)) = ½(12×11)
= ½×132
= 66
Sorting is an everyday activity in which the efficiency of the algorithm used is very important. There are many sorting algorithms designed for use on computers, and there are computer packages available that enable us to compare the merits of the merits of the various algorithms.
In many situations, we want to sort some 'things' into a certain order. We might want to put books or CDs into alphabetical order, or we may be using a packing algorithm that requires the data to be pre-sorted. With a small amount of data, this is easy to do by sight. For larger amounts of data we need the help of clearly defined algorithms.
So, now we will discuss about sorting using interchange sort algorithm and bubble sort algorithm. From these types of sorting, we will give explanation about these types deeply and discuss how we went to sort the pupils of 4 Pintar.
From the name list that we take, we must sort it using two way of sorting which is interchange sort algorithm and bubble sort algorithm. Sorting name is actually for us easily to see the list whether it is ascending or descending.
This is the name list of 4 Pintar pupils from Sekolah Kebangsaan Taman Kota Jaya, Kota Tinggi, Johor. There are 22 pupils in this class and the name list is not yet arranges according alphabetical order from A to Z. So, now we will sort the name list using two ways which are bubble sort algorithm and interchange sort algorithm.
No. NAME
1 Ahmad Johari Bin Yazid
2 Muhammad Syazwani Bin Abdul Wahab
3 Muhammad Nor Islam Bin Hussin
4 Aini Nazira Binti Shamsul
5 Kahirul Hamizan Bin Abdul Halim
6 Muhammad Qiyyam Bin Mohd Noor
7 Mohd Fikri Bin Mohd Idris
8 Emirul Iqbal Irman Fitri Bin Sulaiman
9 Anisa RAmadhany Binti Basrizal
10 Mohd Afiq Haikal Bin Mohd Lusli
11 Muhamad Firdaus Bin Ishak
12 Muhammad Haris Bin Azman
13 Luqman Hakimi Bin Armani
14 Nur Farahana Binti Jamain
15 Nurul Fatihah Binti Kamalrudin
16 Muhammad Ariffin Bin Abdul Rahman
17 Nurul Farahin Binti Azli
18 Muhammad Caniel Bin Rihaizan
19 Muhd Haziq Hamdani Bin Abd Jabar
20 Nur Syaidatul Alia Binti Rithaudeen
21 Wan Azizul Hazairie Bin Azizul
22 Muhammad Hazim Bin Azanam
Interchange Sort Algorithm
What is interchange sort algorithm? Interchange sort algorithm is one of the types of sorting data. In this method, we find the smallest number in the list or set is found and interchange it with the number in the first position. Then we find the second smallest number excluding the first is found, and swap it with the number in the second position. This process continues until list is sorted.
In example, we get the following (numbers in italics have been verified to be in the correct position by the algorithm):
Pass Order
0 7 5 2 4 10 1
1 1 5 2 4 10 7
2 1 2 5 4 10 7
3 1 2 4 5 10 7
4 1 2 4 5 10 7
5 1 2 4 5 7 10
Number of comparisons: 0 + 1 + 2 + 3 + 4 + 5 = 15 comparisons.
This example requires 15 comparisons to sort six numbers.
There are a few things to notice here. Firstly, the fourth pass did not change the order of the data - it merely checked that 5 were in the correct position. Secondly, the final pass verifies the position of two numbers - if the
second largest number has been put in the correct position, the largest must also be in the correct position. Because of this, we know that a set of m numbers will need m -1 passes to be put in the correct order.
The comparisons we are making between pairs of numbers are, in a sense, hidden in this algorithm. In each pass we need to find the smallest number of the remaining (unsorted) set3. This will need m - n comparisons on the nth pass, hence the total number of comparisons needed will be:
(m -1) + (m -2) + … + (m -[m -2]) + (m -[m -1]) = (m -1) + (m -2) + … + 2 + 1
= ½(m×(m -1))
So for our six-item example, this gives:
½(m×(m -1)) = ½(6×5)
= ½×30
= 15
If we had twice as much data (that is, 12 items) we would have:
½(m×(m -1)) = ½(12×11)
= ½×132
= 66
No comments:
Post a Comment