As we discussed above, anything that can store data can be called as a data strucure, hence Integer, Float, Boolean, Char etc, all are data structures. They are known as Primitive Data Structures. Then we also have some complex Data Structures, which are used to store large and connected data. Some example of Abstract Data Structure are :

All these data structures allow us to perform different operations on data. We select these data structures based on which type of operation is required. We will look into these data structures in more details in our later lessons.

Sorting is nothing but storage of data in sorted order, it can be in ascending or descending order. The term Sorting comes into picture with the term Searching. There are so many things in our real life that we need to search, like a particular record in database, roll numbers in merit list, a particular telephone number, any particular page in a book etc.
Sorting arranges data in a sequence which makes searching easier. Every record which is going to be sorted will contain one key. Based on the key the record will be sorted. For example, suppose we have a record of students, every such record will have the following data:
Roll No.
Name
Age
Class

Here Student roll no. can be taken as key for sorting the records in ascending or descending order. Now suppose we have to search a Student with roll no. 15, we don't need to search the complete record we will simply search between the Students with roll no. 10 to 20.

**Types of Sorting Techniques : **

There are many types of Sorting techniques, differentiated by their efficiency and space requirements. Following are some sorting techniques which we will be covering in next sections.Bubble Sort
Insertion Sort
Selection Sort

Here Student roll no. can be taken as key for sorting the records in ascending or descending order. Now suppose we have to search a Student with roll no. 15, we don't need to search the complete record we will simply search between the Students with roll no. 10 to 20.

There are many types of Sorting techniques, differentiated by their efficiency and space requirements. Following are some sorting techniques which we will be covering in next sections.

Bubble Sort is an algorithm which is used to sort N elements that are given in a memory for eg: an Array with N number of elements. Bubble Sort compares all the element one by one and sort them based on their values.
It is called Bubble sort, because with each iteration the smaller element in the list bubbles up towards the first place, just like a water bubble rises up to the water surface.
Sorting takes place by stepping through all the data items one-by-one in pairs and comparing adjacent data items and swapping each pair that is out of order.

**Sorting using Bubble Sort Algorithm : **
Let's consider an array with values {5, 1, 6, 2, 4, 3}

int a[6] = {5, 1, 6, 2, 4, 3}; int i, j, temp; for(i=0; i<6; i++) { for(j=0; j<6-i-1; j++) { if( a[j] > a[j+1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; } } } //now you can print the sorted array after this

It is a simple Sorting algorithm which sorts the array by shifting elements one by one.

Following are some of the important characteristics of Insertion Sort.

1. It has one of the simplest implementation

2. It is efficient for smaller data sets, but very inefficient for larger lists.

3. Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.

4. It is better than Selection Sort and Bubble Sort algorithms.

5. Its space complexity is less, like Bubble Sorting, inerstion sort also requires a single additional memory space.

6. It is Stable, as it does not change the relative order of elements with equal keys.

**Sorting using Insertion Sort Algorithm :**

Following are some of the important characteristics of Insertion Sort.

1. It has one of the simplest implementation

2. It is efficient for smaller data sets, but very inefficient for larger lists.

3. Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.

4. It is better than Selection Sort and Bubble Sort algorithms.

5. Its space complexity is less, like Bubble Sorting, inerstion sort also requires a single additional memory space.

6. It is Stable, as it does not change the relative order of elements with equal keys.

int a[6] = {5, 1, 6, 2, 4, 3}; int i, j, key; for(i=1; i<6; i++) { key = a[i]; j = i-1; while(j>=0 && key < a[j]) { a[j+1] = a[j]; j--; } a[j+1] = key; }

Selection sorting is conceptually the most simplest sorting algorithm.

This algorithm first finds the smallest element in the array and exchanges it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continues in this way until the entire array is sorted.

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

**Sorting using Selection Sort Algorithm :**

This algorithm first finds the smallest element in the array and exchanges it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continues in this way until the entire array is sorted.

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

void selectionSort(int a[], int size) { int i, j, min, temp; for(i=0; i < size-1; i++ ) { min = i; //setting min as i for(j=i+1; j < size; j++) { if(a[j] < a[min]) //if element at j is less than element at min position { min = j; //then set min as j } } temp = a[i]; a[i] = a[min]; a[min] = temp; } }

Stack is an abstract data type with a bounded(predefined) capacity. It is a simple data structure that allows adding and removing elements in a particular order. Every time an element is added, it goes on the top of the stack, the only element that can be removed is the element that was at the top of the stack, just like a pile of objects.

**Basic features of Stack :**

1. Stack is an ordered list of similar data type.

2. Stack is a LIFO structure. (Last in First out).

3. push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.

4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

**Applications of Stack : **

The simplest application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack. There are other uses also like : Parsing, Expression Conversion(Infix to Postfix, Postfix to Prefix etc) and many more.

**Implementation of Stack : **

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size.

1. Stack is an ordered list of similar data type.

2. Stack is a LIFO structure. (Last in First out).

3. push() function is used to insert new elements into the Stack and pop() is used to delete an element from the stack. Both insertion and deletion are allowed at only one end of Stack called Top.

4. Stack is said to be in Overflow state when it is completely full and is said to be in Underflow state if it is completely empty.

The simplest application of a stack is to reverse a word. You push a given word to stack - letter by letter - and then pop letters from the stack. There are other uses also like : Parsing, Expression Conversion(Infix to Postfix, Postfix to Prefix etc) and many more.

Stack can be easily implemented using an Array or a Linked List. Arrays are quick, but are limited in size and Linked List requires overhead to allocate, link, unlink, and deallocate, but is not limited in size.

Queue is also an abstract data type or a linear data structure, in which the first element is inserted from one end called REAR(also called tail), and the deletion of exisiting element takes place from the other end called as FRONT(also called head). This makes queue as FIFO data structure, which means that element inserted first will also be removed first.

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

**Basic features of Queue :**

1. Like Stack, Queue is also an ordered list of elements of similar data types.

2. Queue is a FIFO( First in First Out ) structure.

3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.

4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

**Applications of Queue :**

1.Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :

2. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.

3. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service served.

The process to add an element into queue is called Enqueue and the process of removal of an element from queue is called Dequeue.

1. Like Stack, Queue is also an ordered list of elements of similar data types.

2. Queue is a FIFO( First in First Out ) structure.

3. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.

4. peek( ) function is oftenly used to return the value of first element without dequeuing it.

1.Queue, as the name suggests is used whenever we need to have any group of objects in an order in which the first one coming in, also gets out first while the others wait for there turn, like in the following scenarios :

2. Serving requests on a single shared resource, like a printer, CPU task scheduling etc.

3. In real life, Call Center phone systems will use Queues, to hold people calling them in an order, until a service served.