Sorting Techniques in Pascal PDF

Preview

Summary

lecture notes...

Description

http://www.studytonight.com/data-structures/queue-data-structure Sorting in Pascal In computer science, sorting is sorting is any process of arranging items according to a certain sequence or in different sets, and therefore, it has two common, yet distinct meanings: 1. ordering: arranging items of the same kind, class or nature, in some ordered sequence, 2. categorizing: grouping and labeling items with similar properties together (by sorts) Techniques in Pascal Bubble Sort In a bubble sorting algorithm, the elements of the list gradually bubble (or rise) to their proper location in the array, like bubbles rising in a glass of soda. It is called bubble sort because with each iteration the smaller element in the list bubbles towards the first position just like water bubble rise up to the water surface. It compares all elements one by one and sorts them based on their value.

Advantages of the Bubble Sort i.

The bubble sort requires very little memory other than that which the array or list itself occupies.

ii. iii.

The bubble sort is comprised of relatively few lines of code. The bubble sort is good for testing whether or not a list is sorted or not.

1

iv.

The same applies for data sets that have only a few items that need to be swapped a times.

Disadvantages of the Bubble Sort i.

The main disadvantage of the bubble sort method is the time it requires.

ii.

Additionally, the presence of turtles can severely slow the sort.

Example 1 Program bubbleSort (input, output); (*Define type constant size of array*) const size=10; (*Define array type*) type arrtype = array[1..size] of integer; (*Declare variables for i(array data placeholder), j(count variable) and*) (*temp(swapped data placeholder*) var i, j, temp : integer; arr : arrtype;

(*start of program*) begin

(*Read array*) for i:=1 to size do readln(arr[i]);

(*Main bubble sort loop*) for j:=1 to size-1 do 2

for i:=1 to size-1 do if arr[i+1]>arr[i] then begin (*change > to < if you want ASCENDING order*) temp:=arr[i]; arr[i]:=arr[i+1]; arr[i+1]:=temp; end;

(*Write Output*) for j:=1 to size do writeln(arr[j]);

end.

Example 2 program bubble_sort (i, o); var a: array [1..6] of integer; temp, j, i: integer; begin writeln (‘enter the six array elements ‘); for i: = 1 to 6 do {loop to enter array elements from the keyboard} readln (a [i]); (*bubble sort- ascending*) for i:= 1 to 6 do begin 3

for j: = 1 to 5 do begin if (a[j] > a [j+1]) then begin temp: = a[j]; a [j]: = a [j+1]; a [j+1]: = temp; end; end; end; writeln (‘the sorted list’); for i: = 1 to 6 do writeln (a [i]); end. Example 3 Using a Procedure to bubble Sort

program example1(i, o); type list = array [1..6] of integer; var a: list; j, i: integer; procedure bubble_sort (data: list); 4

var temp:integer; begin (*bubble sort- ascending*) for i:= 1 to 6 do begin for j:= 1 to 5 do begin if (data [j] > data [j+1]) then begin temp:= data [j]; data [j]:= data [j+1]; data [j+1]:= temp; end; end; end; writeln ('the sorted list'); for i:= 1 to 6 do writeln (data [i]); end; begin writeln ('enter the six array elements'); for i:= 1 to 6 do {loop to enter array elements from the keyboard} readln (a [i]);

5

bubble_sort(a); (*procedure call*) end. Selection Sort Algorithm This technique first finds the smallest item in the array list and exchanges it with the first element in the list then finds the second smallest element in the and then exchange it with the element second position and continues in this way until the whole is sorted.

In the first pass the smallest element is 1 so it is placed at the first position, then leave the first element, smallest element is searched from the rest of the elements, 3 is the smallest so then it is placed at the second position. Then we leave 1 and 3 from the rest of the elements, we search for the smallest from the elements and put it in the third position and keep doing this until the array is sorted.

Example 1 Program Selection_Sort;

Var a: array [1..6] of Integer; 6

Temp, Smallest, Loc, j, i: Integer; Begin Writeln (‘Enter the six Array Elements ‘); For i: = 1 To 6 Do {Loop to enter array elements from the keyboard} Readln (a [i]); (*Selection Sort- Ascending*) For i: = 1 To 6 Do Begin Smallest: = A [i]; For j: = i To 5 Do Begin If (Smallest > A [j+1]) Then Begin Smallest: = A [j+1]; Loc: = j+1; End End; Temp: = A[i]; A [i]: = Smallest; A [Loc]: = Temp; End; Writeln (‘The Sorted List’); For i: = 1 To 6 Do Writeln (A [i]);

7

End.

Example 2 program sel_sort; uses crt; var A:Array [1..80] of integer; k,temp,j,n,loc,m,i:integer; begin clrscr; writeln("ENTER THE LENGTH OF ARRAY "); read(n); writeln("ENTER ",n," NUMBERS "); for i:=1 to n do read(A[i]); for k:=1 to n-1 do begin m:=A[k]; loc:=k; for j:=k+1 to n do begin if m>A[j] then begin m:=A[j]; loc:=A[j]; 8

loc:=j; end; end; temp:=A[k]; A[k]:=A[loc]; A[loc]:=temp; end; writeln; writeln("THE SORTING ORDER IS "); writeln; for i:=1 to n do write(A[i]:3); end.

Insertion Sort Algorithm This is the simplest algorithm which sorts arrays by shifting elements one by one.

Characteristics i.

Simplest algorithm implementation

ii.

Efficient for smaller data sets but inefficient for larger sets

iii.

It is adaptive meaning that it reduces the number of steps if given and a partially sorted list hence it increase its efficiency

iv.

It is better that bubble and selection sort algorithms

9

v.

Its space complexity is less. Algorithms like bubble and insertion requires more space at execution time.

vi.

It is stable i.e. does not change the relative order of elements with equal

Quick sort algorithms Also called partition exchange sort. As the name states it quickly sorts elements in the list. It is based on divide and conquer technique. This algorithm divides the list into three main parts.

i.

Elements less than the pivot element

ii.

Pivot element

iii.

Elements greater than the pivot element

Characteristics 10

i.

Quick sort is not stable search

ii.

It is very fast and requires very less additional space.

Example

6

8

17

14

25

63

37

52

In the list of elements, mentioned in below example, we have taken 25 as pivot. So after the first pass, the list will be changed like this.

6

8

17

14

25

63

37

52

Hnece after the first pass, pivot will be set at its position, with all the elements smaller to it on its left and all the elements larger than it on the right. Now 6 8 17 14 and 63 37 52 are considered as two separate lists, and same logic is applied on them, and we keep doing this until the complete list is sorted.

11

Example 1 Program insertion_Sort (I, O); VAR A: ARRAY [1..6] OF Integer; Temp, key, j, i: Integer; Begin Writeln (‘Enter the six Array Elements ‘); For i: = 1 To 6 Do {Loop to enter array elements from the keyboard} Readln (A [i]); (*Insertion Sort- Ascending*) For k: = 1 To 6 Do Begin For i: = 2 To 6 Do Begin 12

For j: = 1 To i-1 Do Begin If (A[j] > A [j+1]) Then Begin Temp: = A[j]; A [j]: = A [j+1]; A [j+1]: = Temp; End; End; End; End; Writeln (‘The Sorted List’); For i: = 1 To 6 Do Writeln (A [i]);

End.

Merge Sort Algorithm

Merge Sort follows the rule of Divide and Conquer. But it doesn't divide the list into two halves. In merge sort the unsorted list is divided into N sublists, each having one element, because a list of one element is considered sorted. Then, it repeatedly merge these sublists, to produce new sorted sublists, and at lasts one sorted list is produced.

i.

Merge Sort is quite fast, and has a time complexity.

13

ii.

It is also a stable sort, which means the equal elements are ordered in the same order in the sorted list.

14...