Sorting and Searching
1
Sorting a List of numbers
Searching a number in a given List
2
Sorting of a List
• Sorting data either in ascending or descending order is the important
computing application that can be achieved by various ways.
Example
Bubble sort Method
In above visualization , smaller values gradually move upward or bubble to the
top like an air bubble in water and larger values sink down to the bottom of the
array. 3
Program #define SIZE 10
int main ()
{ int data[ SIZE ], i, j, temp;
printf(Enter data items:\n");
for ( i = 0; i < SIZE; ++i)
scanf("%4d", data[ i ]);
for (i = 1; i < SIZE; ++i) //loop for number of passes
{ for (j = 0; j < SIZE - 1; ++j)
{ if (data[ j ] > data[ j + 1]) //comparing and swapping
{ temp = data[ j ];
data[ j ] = data[ j + 1 ];
data[ j + 1 ] = temp;
}
}}
printf("\nData items in ascending order:\n");
for (i= 0; i < SIZE; ++i)
printf("%4d", data[ i ]);
return 0; } 4
Other Methods: Insertion Sort
works the way we sort
playing cards in our hands.
5
Other Method:
Selection Sort
This method sorts an array by
repeatedly finding the minimum
element (considering ascending
order) from unsorted part and
putting it at the beginning.
6
Next example
Selection method maintains two subarrays in a given array.
i) The subarray which is already sorted.
ii) Remaining subarray which is unsorted.
In every iteration, the minimum element (considering ascending order) from
the unsorted subarray is picked and moved to the sorted subarray. 7
Other methods of Sorting for self learning
Selection Sort- C
C implementation: https://youtu.be/088_oErA6Rw
Insertion Sort- Basics: https://youtu.be/h1o2Am7QD_s
C implementation: https://youtu.be/QyPifvRjbRw
8
Searching in a List
• a searching algorithm which is used to detect the presence of a
number in an array and if present, it locates its position in that array.
• method compares each element of the array with the search query
comparing every element until the number is found and located.
9
#define SIZE 10 Program
int Search(int A[], int size, int key);
int main()
{ int data[ SIZE ], i, temp;
int searchKey; //value to search in the array
printf(Enter data items:\n");
for ( i = 0; i < SIZE; ++i)
scanf("%4d", data[ i ]); //search function code
int Search(int A[], int size, int key)
printf("Enter integer to search for: ");
{ int j;
scanf("%d", &searchKey);
for (j = 0; j < size; ++j)
{
//call Search function
if ( a[ j ] == query)
temp = Search(data, searchKey, SIZE);
{
if ( temp != -1) //condition for displaying result
return j; //return location of value
printf("Found value in element %d.", temp);
}
else
}
printf("Value not found.");
return -1; //value not found
return 0;
}
}
10
To do Task
1. Write program of bubble, selection and insertion methods
of sorting the list of given numbers.
2. Also re-write above programs using at least three
functions.
3. Write program of searching an element in a list of given
two dimensional array using minimum three functions.
11
