SMT.R.S.B.
ARYA VIDYA MANDIR , JUHU
Computer Applications – Std X
Sorting Algorithms
Sorting is the process of arranging an array values in ascending or descending order.
Types of Sorting :
1. Selection or simple sort
2. Bubble sort
1. Selection Sorting : If the array is to be arranged in ascending order, the smallest element
needs to be selected and exchanged with the first position element in the array. Again, the
smallest element from the remaining elements is selected and exchanged with second array
element. The process continues till all elements are arranged.
Algorithm for selection sort :
For each element in the list from first to second last
Set the min value equal to the current element
Store the index of the current element
For each element in the list from the current element + 1 to the last element in the list
If element {inner loop index] < min value
Set the min value = element [ inner loop index]
Save the index of the new found min value
End If
End for
Swap the current value with the new minimum value.
End for
Eg.
3 9 6 1 2 ( Here, 1 and 3 are swap)
1 9 6 3 2 ( Here, 2 and 9 are swap)
1 2 6 3 9 ( Here, 3 and 6 are swap)
1 2 3 6 9 Now, the values are in ascending order.
2. Bubble Sort : The adjacent element of the array are compared. If array needs to be
arranged in ascending order and left element(say a[0]) is greater than the right element (say
a[1]) , they need to be exchanged(process of exchanging values is called Swapping).
Algorithm for bubble sort :
Set the interchange counter to 0
For the first element in the list to one less than the last element in the list(i index)
For the second element in the list to the last index(j index)
If value at j< the value at j - 1
Swap the items
Increase the interchange counter
End If
End for
End for
Return the interchange counter
Eg :
6 5 4 3 2 1
5 6 4 3 2 1 ( no need to bubble back as 5 6 is in ascending order)
5 4 6 3 2 1 ( must bubble back as 5 4 6 is not in ascending order)
4 5 6 3 2 1 {left hand side sorted)
4 5 3 6 2 1 ( must bubble back as 5 4 3 6 is not in ascending order)
4 3 5 6 2 1 so on ……
3 4 5 6 2 1
3 4 5 2 6 1
.
.
.
Selection sort Bubble Sort
1. The selection sort method repeatelly In bubble sort, the smallest key is moved
selects the smallest key in the remaing into its final position and it is exchanged
unsorted array.The smallest keys are with initial key earlier placed in that
placed in orderly position. position.
2. In the selection sort a separate In bubble sort does not require any
temporary memory area is required for separate memory are for sorting.
sorting. Therefore, requires more space
for working.
public class ArraySelSort
{
int n[];
public ArraySelSort(int n1[])
{
n=n1;
}
public void selectioSort()
{
int temp;
int size=n.length;
for(int i=0;i<size-1;i++)
{
for(int x=i+1;x<n.length;x++)
{
if(n[x]>n[i]) //Sorting in desc order
{ //for ascending order if(n[i]>n[x])
temp=n[i];
n[i]=n[x];
n[x]=temp;
}
}
}
for(int k=0;k<size;k++)
{
System.out.println(n[k]);
}
}
}
//Program based on bubble sort in ascending oder
import java.util.*;
public class Temperature
{
Scanner sc=new Scanner(System.in);
public void sort()
{
String city[]=new String[5];
int a[]=new int [5];
String t2;
int t1;
System.out.print("Enter city and temp");
for(int i=0;i<5;i++)
{
city[i]=sc.next();
a[i]=sc.nextInt();
}
for(int i=0;i<city.length-1;i++)
{
for(int j=0;j<city.length-1;j++)
{
if(a[j+1]< a[j])
{
t1=a[j];
a[j]=a[j+1];
a[j+1]=t1;
t2=city[j];
city[j]=city[j+1];
city[j+1]=t2;
}
}
}
for(int i=0;i<city.length;i++)
{
System.out.println(city[i] + " "+ a[i]);
}
}
}
Ex :
1. Given array 12,3,8,5 What will be array like after two passes of selection sort?
Ans : 3,5,8,12
2. Given an array 12,3,8,5. What will be array like after two passes of bubble sort?
Ans : 3,8,12,5
3. An array 18,13,2,9,5 is 13,2,9,18,5 after three passes. What sorting technique is
applied on it?
4. WAP to bubble sort the following set values of ascending order [ICSE 2005]
5. WAP to accept 15 integers from the keyboard assuming that no integer entered is
a zero. Perform selection sort on the integers and then print in ascending
order.[ICSE 2006]
6. The following array of integers is to be arranged in ascending order using the
bubble sort technique : 26 21 20 23 29 17
Give the content of the array at the end of each iteration. Do not write algorithm.
Program :
1) WAP to input and store the weight of ten people. Sort and display them in descending
order suing selection sort technique.
2) WAP to input 10 integers in an array and sort them in descending order suing the
bubble sort technique.
3) WAP to input city names and their corresponding capital in two different SDA, Sort
these names in alphabetical order using the bubble sort technique.
4) WAP to input student names and their corresponding marks in two different SDA,
Sort these names in alphabetical order using the selection sort technique.
SK
