SORTING ALGORITHMS

Write an algorithm to sort an array by using Bubble Sort Technique

BUBBLE (DATA, N)
Here DATA is an array with N elements. This algorithm sorts the elements in DATA.

1.      Start

2.      Repeat step 3 and 4 for K = 1 to N – 1:

3.      [Initialize pass pointer PTR] Set PTR := 1

4.      [Execute Pass] Repeat while PTR <= N – K

IF DATA[PTR]>DATA[PTR + 1], then:

Interchange DATA[PTR] and DATA[PTR + 1]

[End of If structure]

Set PTR:=PTR +1

[End of Step 3 loop]

[End of Step 1 Loop]

5.      Return

Write an algorithm to sort an array by using Selection Sort Technique

SELECTION(A, N)
This algorithm sorts an array A with N elements.

1.      Start

2.      Repeat steps 3 and 4 for
k = 1 to N – 1

3.      Set Min := A[k] and
LOC := k

4.      Repeat for j = k+1 to N:

If Min >A[j], then:

Set Min := A[j] and
LOC := J

[End of if structure]

[End of step 4 Loop]

5.      [Interchange A[k]
and A[LOC]]

Set Temp := A[k]

Set A[k] := A[LOC]

Set A[LOC] := Temp

[End of step 2 Loop]

6.      Return

Write an algorithm to sort an array by using Insertion Sort Technique

INSERTIONSORT (A , N)
This algorithm sorts the array A with N elements

1.      Start

2.      Set A:= -infinite

3.      Repeat steps 4 to 6 for K=2 to N:

4.      Set TEMP := A[K] and PTR := K – 1

5.      Repeat while
TEMP < A[PTR] :

[Moves element forward] Set A[PTR + 1]:= A[PTR]

Set PTR := PTR – 1

[End of step 5 Loop]

6.      [Inserts element in proper place]
Set A[PTR + 1]:= TEMP

[End of step 3 Loop]

7.      Return

Write an algorithm to sort an array by using Quick Sort Technique

QUICKSORT ( A, N)
This algorithm sorts an array A with N elements. LOWER and UPPER are the two stacks maintained for storing the lower and upper indexes of list or sublist

1.      [Initialize] Set TOP := 0

2.      [Push boundary values of A onto stacks when A has 2 or more elements]

If N > 1, then:

Set TOP := TOP + 1
LOWER := 1 and
UPPER := N

3.      Repeat while TOP != NULL

[Pop sub list from stacks]

Set BEG := LOWER[TOP], END := UPPER[TOP] and

TOP := TOP-1

4.      Call QUICK(A, N, BEG, END, LOC)

5.      [Push left sub list onto stacks when it has 2 or more elements]

If BEG < LOC-1, then :

Set TOP := TOP+1,
LOWER[TOP]:= BEG
UPPER[TOP]:= LOC-1

[End of If structure]

6.      [Push right sub list onto stacks when it has 2 or more elements]

If LOC+1 < END, then :

Set TOP := TOP+1, LOWER[TOP]:= LOC+1,

UPPER[TOP]:= END

[End of If structure]

[End of Step 3 loop]

7.      Return

QUICK(A, N, BEG, END, LOC)
Here A is an array with N elements. Parameters BEG and END contains the boundary values of the sublist of A to which this procedure applies. LOC keeps track of the position of the first element A[BEG] of the sublist during the procedure. The local variables LEFT and RIGHT will contain the boundary values of the list of elements that have not been scanned.

1.      [Initialize]. Set LEFT:=BEG, RIGHT:=END and LOC:=BEG

2.      [Scan from right to left]

(a) Repeat while A[LOC] <= A[RIGHT] and LOC != RIGHT:

RIGHT:=RIGHT-1

[End of Loop]

(b) If LOC=RIGHT, then: Return

(c) If
A[LOC] > A[RIGHT], then:

(i) [Interchange A[LOC] and A[RIGHT] ]
Set TEMP := A[LOC]

Set A[LOC] := A[RIGHT]

Set A[RIGHT] := TEMP

(ii) Set LOC := RIGHT

(iii) Go To Step 3

[End of If Structure]

3.      [Scan from left to right]

(a) Repeat while A[LEFT] <= A[LOC] and LEFT != LOC:

Set LEFT := LEFT+1

[End of Loop]

(b) If LOC = LEFT, then: Return

(c) If A[LEFT] > A[LOC], then

(i) [Interchange A[LEFT] and A[LOC] ]

Set TEMP := A[LOC]

Set A[LOC] := A[LEFT]

Set A[LEFT] := TEMP

(ii) Set LOC := LEFT

(iii) Go To Step 2(QUICKSORT(A,N)

[End of If Structure]