BIT-Birla Institute of Technology Mesra

BIT-Birla Institute of Technology Mesra

Introduction to Insertion Sort

Here’s Insertion Sort, in Ruby, Java and C. It has a Worst and Average Case Scenario Complexity of Theta(n^2) (or Theta n-squared). It is efficient for smaller data sets while larger data sets would require a lot of time for sorting.

Without further delay, here’s the algorithm;
INSERTION SORT (PSEUDO-CODE)
A = [1,5,3,7,6,2,8,9,10,4]
print “Initial Array Order ” + A
for j = 1 to A.length
{
i = j-1
key = A[j]
while i>=0 && A[i]>key
{
A[i+1] = A[i]
i = i-1
}
A[i+1] = key
}
print “Sorted Array Order “+ A

OUTPUT>> [1,2,3,4,5,6,7,8,9,10]
Note: The above algorithm assumes a Zero indexing for the Array. For One indexed Arrays, alter the for loop to -
“for j = 2 to A.length”
and alter the while loop to -
“while i>0 && A[i]>key”

Now, Insertion Sort in Ruby;
INSERTION SORT (RUBY)
A = [1,5,3,7,6,2,8,9,10,4]
p “Initial Array Order”
p A
for j in 1…A.length
i = j-1;
key = A[j];
while i>=0 && A[i]>key
A[i+1] = A[i];
i = i-1;
end
A[i+1] = key;
end
p “Sorted Array Order”
p A

InsertionSort (Java)
public class InsertionSorting
{
public static void main( String[] args )
{
int A[] = { 10, 9, 5, 7, 3, 1 };
System.out.printf(“\nInitial Array:\n”);
for( int k=0;  k{
System.out.printf( “%d, “, A[k]);
}
for( int j=1;  j{
int i = j-1;
int key = A[j];
while((i>=0)&&(A[i]>key))
{
A[i+1] = A[i];
i=i-1;
}
A[i+1] = key;
}
System.out.println(“\nFinal Array:”);
for( int k=0;  k{
System.out.printf(“%d, “,A[k]);
}
}
}

INSERTION SORT (C)
//Insertion Sort
void main()
{
int A[6] = { 10, 5, 7, 3, 4, 1 };
printf(“\nInitial Array\n”);
for ( int l=0;  l<6;  l++)
{
printf(“%d\n”, A[l]);
}
int j =0;
for( j=1;  j<6;  j++)
{
int i = j-1;
int key = A[j];
while((i>=0)&&(A[i]>key))
{
A[i+1] = A[i];
i=i-1;
}
A[i+1] = key;
}
printf(“\nFinal Array\n”);
for (int k=0; k<6; k++)
{
printf(“%d\n”, A[k]);
}
getch();
}

Related Documents

Images

Comments

Update me for this comment
Share your college study materials & notes
Post Now
Campus News & Events
  • Study material
    Colleges sharing lecture notes, Study material, file, assignment etc.
    Study material
  • Educational videos
    College student sharing a great video to help peers study.
    Educational videos
  • Lecture PPT’s
    Presentations shared by students of this college for all other students.
    Lecture PPT’s
  • Ask & clarify doubts
    Peer asking, answering & questing related to the study topic, Building world's most educative database.
    Ask & clarify doubts