01-10-2012, 12:23 PM
SORTING
sorting.ppt (Size: 3.21 MB / Downloads: 23)
INTRODUCTION
SORTING : Arranging the data in a particular order.
Applications : Telephone directory, dictionaries, book indexes,
bank accounts, payrolls, student lists.
Properties of Sorting Algorithms :
1. Number of comparisons to be made
2. Number of data movements
Objectives :
Minimize the number of data movements.
Programming time
Execution time
Memory utilized.
Sorting is the arrangement of data in some order. Different methods
Are used to sort the data in ascending or descending order.
They are divided into two categories :
Internal sorting : sorting data in main memory.
External sorting : sorting large amount of data that some data is
present in main memory and some is kept in
auxiliary memory.
INTERNAL SORTING METHODS
Insertion sort
Selection sort
Exchange sort ( Bubble Sort)
Shell sort
Heap sort
Merge sort
Quick sort
INSERTION SORT
Inserting a particular element at the appropriate position.
If there are n items in the array, then (n-1) iterations are used.
ALGORITHM
Start.
Assume that there are n elements in the list of items to be sorted.
Set i=1, j=0.
EXCHANGE SORT
Basic operation of Exchange sort is the exchange of adjacent pair of elements
Overall sort consist of a number of passes over the data
Each pass starts at one end of the array and works toward the other end
Each pair of elements that are out of order are exchanged
The elements with largest value are moving slowly or bubbling to the top
If no exchanges are made during one pass over the data, the data have been sorted and process terminates
Merging means combining two sorted lists into one sorted list.
The elements from both the sorted lists are compared. The smaller
of both the elements is then stored in the third array.
ALGORITHM
Accept the total number of elements in the array a1 i.e., n1.
Accept the n1 different elements of the array a1.
Accept the total number of elements in the array a2. Let it be n2.
Accept the n2 different elements of the array a2.
Sort the array a1 , a2.
Now perform the merge sort algorithm on arrays a1 and a2. The
result will be in a3.