[go: up one dir, main page]
Scribd
Upload
34 views9 pages

Table Processing-Searching & Sorting

The document discusses various sorting and searching algorithms, including linear search, binary search, selection sort, and bubble sort. Linear search sequentially compares elements to the search key. Binary search compares the target to the middle element and recursively searches left or right halves. Selection sort finds the minimum element and swaps it into the sorted portion. Bubble sort compares adjacent elements and swaps any out of order to bubble largest to the end.

Uploaded by

ankur kashyap
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
34 views9 pages

Table Processing-Searching & Sorting

The document discusses various sorting and searching algorithms, including linear search, binary search, selection sort, and bubble sort. Linear search sequentially compares elements to the search key. Binary search compares the target to the middle element and recursively searches left or right halves. Selection sort finds the minimum element and swaps it into the sorted portion. Bubble sort compares adjacent elements and swaps any out of order to bubble largest to the end.

Uploaded by

ankur kashyap
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 9

Table Processing- Searching &

Sorting
Linear Search
Linear search works on the design
principle of brute force and it is one of
the simplest searching algorithm as well
Linear search is also called as a
sequential search as it compares the
successive elements of the given set
with the search key

5/1/2006 Computer System Software CS 012 BE CS 7th Semester 2


Linear Search
1. Begin
2. For i = 1 to n do
2.1 If (target = a[i]) then End with output
as i
3. End with output as none

5/1/2006 Computer System Software CS 012 BE CS 7th Semester 3


Binary Search
Binary Search takes a sorted array as the input
It works by comparing the target (search key)
with the middle element of the
array and terminates if it is the same, else it
divides the array into two sub arrays and
continues the search in left (right) sub array if
the target is less (greater) than the middle
element of the array.

5/1/2006 Computer System Software CS 012 BE CS 7th Semester 4


Binary Search
Begin
2. Set left = 1, right = n
3. While (left right) do
3.1 m = floor(( left + right )/2)
3.2 If (target = a[m]) then End with output as m
3.3 If (target < a[m]) then right = m-1
3.4 If (target > a[m]) then left = m+1
3. End with output as none

5/1/2006 Computer System Software CS 012 BE CS 7th Semester 5


Selection Sort
All sorting algorithms start with the given input
array of data (unsorted array) and after each
iteration extend the sorted part of the array by
one cell. The sorting algorithm terminates
when sorted part of array is equal to the size
of the array
In selection sort, the basic idea is to find the
smallest number in the array and swap this
number with the leftmost cell of the unsorted
array, thereby increasing the sorted part of
the array by one more cell
5/1/2006 Computer System Software CS 012 BE CS 7th Semester 6
Selection Sort
To sort the given array a[1…n] in ascending
order:
1. Begin
2. For i = 1 to n-1 do
2.1 set min = i
2.2 For j = i+1 to n do
2.2.1 If (a[j] < a[min]) then set min = j
2.3 If (i ¹ min) then swap a[i] and a[min]
3. End
5/1/2006 Computer System Software CS 012 BE CS 7th Semester 7
Bubble Sort
Bubble sort works by comparing
adjacent elements of an array and
exchanges them if they are not in order.
After each iteration (pass) the largest
element bubbles up to the last position
of the array. In the next iteration the
second largest element bubbles up to
the second last position and so on
5/1/2006 Computer System Software CS 012 BE CS 7th Semester 8
Bubble sort
1. Begin
2. For i = 1 to n-1 do
2.1 For j = 1 to n-1-i do
2.2.1 If (a[j+1] < a[j]) then swap a[j] and
a[j+1]
3. End

5/1/2006 Computer System Software CS 012 BE CS 7th Semester 9

You might also like