Untitled
unknown
plain_text
5 months ago
24 kB
2
Indexable
## Radix Sort
- we know the counting sort, radix sort is an extension of it.
- In radix sort we make use of stability of counting sort.
- Here first we sort the data on basis of unit digit of numbers and consider remaining digits of number as its satellite data.
- Then similarly we sort on basis of tenth digit data, hundredth digit data, and so on. and finally our array will be sorted at end.
```
329 720 720 329
457 355 329 355
657 436 436 436
839 ----> 457 ----> 839 ------> 457
436 (1th) 657 (10th) 355 (100th) 657
720 329 457 720
355 839 657 839
```
- Time complexity : if n is the numbers and d is the number of digits in the largest number then TC = O(n*d).
## When to use which sorting algorithm.
- Insertion Sort : use when almost sorted array. TC=O(n), SC=O(1).
- Merge Sort : array does not fit completely in RAM(external sorting). TC=O(nlog(n)), SC=O(n).
- Quick Sort : randomised QS is used as general purpose sorting algorithm. Used in C, Unix, Java.
- Counting sort : numbers between small range (0 to K).
- Radix Sort : numbers have multiple digits.
- Bubble Sort : avoid.
---
- Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It was implemented as default sorting algorithm in python. Today it is so popular that it is used in Java SE, Android platform, GNU octave, Google Chrome.
### Question
Q : if we use radix sort to sort n integers in range (n^k/2, n^k), where k is independent of n , the time taken would be?
A : we can represent any number n with log(n) digits in binary. so n^k can be represented in klog(n) digits in binary. The TC of radix sort is O(a x n) , so TC = O(klog(n) x n) , but k is independent of n and can be treated as constant. TC = O(nlog(n)).
# Data Structures.
- A data structure is a data organization, mangement and storage format that enables efficient access and modification. More precisely a data structure is a collection of data values, the relationships among them and the functions operations that can be applied to the data.
Eg : Arrays
- collection of elements of same datatype.
- relationship : elements are ordered in some manner, one after another.
- operations : set, get, traverse, indexing, search.
## Need of data structure
- for efficient storage, access and modification of data.
- suppose we have mapdata about cites and distance between two cities, so how can i store this data efficiently, we need a special data structure : graphs.
- every data structure has its own pros and cons. like we cant grow the size of array dynamically.
## Linked list
(Singlym Doubly, Circular)
- can overcome drawback of array.
- Linked lists can grow dynamically in size.
- Linked list consists of several nodes linked together, each node consists of a value and an address to the next node.
- In Linked list we have a head pointer which points to first node of Linked list, and the last node of linked list points to NULL
- In Linked list the nodes are not stored at continous memory location.
- In c we implement node using structs and other language C++, Java, Python, we make use of classses.
```c
#include<stdio.h>
#include<stdlib.h>
struct node{
int info;
struct node *link;
};
struct node *insert_at_beg(struct node *head, int data){
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
temp->link = head;
head = temp;
return head;
}
struct node* insert_at_end(struct node* head, int data){ //O(n)
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
temp->link = NULL;
if(head == NULL){
head = temp;
return head;
}
struct node *p = head; // to traverse the list.
while(p->link != NULL){
p = p->link;
}
p->link = temp; //linking node at end
return head;
}
//insert node after given node.
struct node *insert_after(struct node *head, int after, int data){
if(head == NULL){
printf("List is Empty. \n");
return head;
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
struct node *p = head;
temp->info = data;
while(p != NULL){
if(p->info == after){
temp->link = p->link;
p->link = temp;
return head;
}
p = p->link;
}
printf("%d not present in List.\n", after);
return head;
}
struct node *insert_at_pos(struct node *head, int pos, int data){
if(pos < 1){
printf("position must be greater than 1");
return head;
}else if(pos == 1){
return insert_at_beg(head,data);
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
struct node* p = head;
int cnt = 1;
while(p->link != NULL){
if(++cnt == pos){
temp->link = p->link;
p->link = temp;
return head;
}
p = p->link;
}
if(++cnt == pos){
temp->link = NULL;
p->link = temp;
return head;
}
printf("Cannot insert %d at position %d, As list has only %d elements.\n", data, pos, --cnt);
return head;
}
struct node *del_node(struct node *head, int data){ //O(n)
//case 1 : List is empty
if(head == NULL){
printf("List is Empty\n");
return head;
}
//case 2 : deletion of head node
struct node *temp;
if(head->info == data){
temp = head;
head = temp->link;
free(temp);
return head;
}
//case 3 : delete inbetween or end node
struct node *p=head;
while(p->link != NULL){
if(p->link->info == data){
temp = p->link; //store the node to be deleted
p->link = temp->link;
free(temp);
return head;
}
p=p->link;
}
printf("Element %d not found in list.\n", data);
return head;
}
// traverse of display all elements in the list
void display(struct node* head){ //O(n)
if(head == NULL){
printf("List is Empty \n");
return;
}
struct node* p;
p = head;
printf("List is : [ ");
while(p != NULL){
printf("%d ",p->info);
p = p->link;
}
printf("].\n");
}
//count number of elements in list.
int count(struct node* head){ //O(n)
int cnt = 0;
struct node* p;
p = head;
while(p != NULL){
p = p->link;
cnt++;
}
return cnt;
}
// search an element in the given list.
void search(struct node* head, int data){
int pos = 1;
struct node* p = head;
while(p != NULL){
if(p->info == data){
printf("Item %d found at position %d\n", data, pos);
return;
}
p=p->link;
pos++;
}
printf("Item %d not found in the list.\n",data);
}
//move last node to front.
struct node *move_to_front(struct node *head){
if(head == NULL || head->link == NULL){
return head;
}
struct node *p=head, *q=NULL;
while(p->link != NULL){
q = p;
p = p->link;
}
q->link = NULL;
p->link = head;
head = p;
return head;
}
int main(){
struct node *head = NULL;
int choice,data,item,pos;
printf("1.Display\n");
printf("2.Count list\n");
printf("3.Search element\n");
printf("4.Insert new node at the beginning\n");
printf("5.Insert new node at the end\n");
printf("6.Insert new node after the given node\n");
printf("7.Insert new node at the given node\n");
printf("8.Delete node\n");
printf("9.Reverse list\n");
printf("10.Quit\n\n");
printf("Enter your choice : ");
scanf("%d", &choice);
while(choice != 10){
switch(choice){
case 1:
display(head);
break;
case 2:
printf("List has %d elements.\n", count(head));
break;
case 3:
printf("Enter the data to find : ");
scanf("%d", &data);
search(head, data);
break;
case 4:
printf("Enter the data to insert at beginning : ");
scanf("%d", &data);
head = insert_at_beg(head,data);
break;
case 5:
printf("Enter the data to insert at end : ");
scanf("%d", &data);
head = insert_at_end(head,data);
break;
case 6:
printf("Insert data after node : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
head = insert_after(head, pos, data);
break;
case 7:
printf("Insert data at node number : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
head = insert_at_pos(head, pos, data);
break;
case 8:
printf("Enter the data to delete : ");
scanf("%d", &data);
head = del_node(head, data);
break;
case 9:
printf("Reversing Single Linked List is time taking. \n");
break;
case 10:
break;
default:
printf("Enter choice less than 10. \n");
}
display(head);
printf("Enter your choice : ");
scanf("%d", &choice);
}
return 0;
}
```
### Drawbacks of Linked list
- It takes more memory than arrays because of the storage used by pointers.
- Nodes in a linked list must be read in order from the beginning (sequential access). Linked list access takes O(n) time , while array takes O(1) time.
- Nodes are stored incontigously, greatly increasing the time required to access individual elements within the list, especially in case of CPU cache , As for arrays, the data is copied from RAM to CPU cache for faster access.
- Difficulties arise in linked lists when it comes to reverse traversing.
## Doubly linked list
### Motivation
- Traverse list in reverse order.
### Defination.
- Doubly linked list is a LL in which we maintain two pointers head and tail. It has structure as `|prev|info|next|`.
```c
#include<stdio.h>
#include<stdlib.h>
struct node{
int info;
struct node *prev;
struct node *next;
};
struct node *insert_at_beg(struct node *head, int data){
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
temp->prev = NULL;
temp->next = head;
if(head){
head->prev = temp;
}
head = temp;
return head;
}
struct node* insert_at_end(struct node* head, int data){ //O(n)
struct node *temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
temp->next = NULL;
if(head == NULL){
head = temp;
return head;
}
struct node *p = head; // to traverse the list.
while(p->next != NULL){
p = p->next;
}
p->next = temp; //linking node at end
temp->prev = p;
return head;
}
//insert node after given node.
struct node *insert_after(struct node *head, int after, int data){
if(head == NULL){
printf("List is Empty. \n");
return head;
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
struct node *p = head;
temp->info = data;
while(p != NULL){
if(p->info == after){
temp->next = p->next;
temp->prev = p;
if(p->next != NULL)
p->next->prev = temp;
p->next = temp;
return head;
}
p = p->next;
}
printf("%d not present in List.\n", after);
return head;
}
// insert node at node number pos.
struct node *insert_at_pos(struct node *head, int pos, int data){
if(pos < 1){
printf("position must be greater than 1");
return head;
}else if(pos == 1){
return insert_at_beg(head,data);
}
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->info = data;
struct node* p = head;
int cnt = 1;
while(p->next != NULL){
if(++cnt == pos){
temp->next = p->next;
temp->prev = p;
if(p->next != NULL)
p->next->prev = temp;
p->next = temp;
return head;
}
p = p->next;
}
if(++cnt == pos){
temp->next = NULL;
temp->prev = p;
p->next = temp;
return head;
}
printf("Cannot insert %d at position %d, As list has only %d elements.\n", data, pos, --cnt);
return head;
}
struct node *del_node(struct node *head, int data){ //O(n)
//case 1 : List is empty
if(head == NULL){
printf("List is Empty\n");
return head;
}
// case 2 : Only one element in list.
struct node *temp;
if(head->next == NULL){
if(head->info == data){
temp = head;
head = NULL;
free(temp);
return head;
}
else{
printf("Element %d not found.\n",data);
}
}
//case 3 : deletion of head node
if(head->info == data){
temp = head;
head = temp->next;
head->prev = NULL;
free(temp);
return head;
}
//case 4 : delete inbetween node
temp = head->next;
while(temp->next != NULL){
if(temp->info == data){
temp->prev->next = temp->next;
temp->next->prev = temp->prev;
free(temp);
return head;
}
temp = temp->next;
}
//case 5 : delete end node
if(temp->info == data){
temp->prev->next = NULL;
free(temp);
return head;
}
printf("Element %d not found in list.\n", data);
return head;
}
// traverse of display all elements in the list
void display(struct node* head){ //O(n)
if(head == NULL){
printf("List is Empty \n");
return;
}
struct node* p;
p = head;
printf("List is : [ ");
while(p != NULL){
printf("%d ",p->info);
p = p->next;
}
printf("].\n");
}
//count number of elements in list.
int count(struct node* head){ //O(n)
int cnt = 0;
struct node* p;
p = head;
while(p != NULL){
p = p->next;
cnt++;
}
return cnt;
}
// search an element in the given list.
void search(struct node* head, int data){
int pos = 1;
struct node* p = head;
while(p != NULL){
if(p->info == data){
printf("Item %d found at position %d\n", data, pos);
return;
}
p=p->next;
pos++;
}
printf("Item %d not found in the list.\n",data);
}
//move last node to front.
struct node *move_to_front(struct node *head){
if(head == NULL || head->next == NULL){
return head;
}
struct node *p=head;
while(p->next != NULL){
p = p->next;
}
p->prev->next = NULL;
p->next= head;
head->prev = p;
p->prev = NULL;
head = p;
return head;
}
// Reversing the linked list
struct node* reverse_linked_list(struct node *head){
return head; // to implement
}
int main(){
struct node *head = NULL;
int choice,data,item,pos;
printf("1.Display\n");
printf("2.Count list\n");
printf("3.Search element\n");
printf("4.Insert new node at the beginning\n");
printf("5.Insert new node at the end\n");
printf("6.Insert new node after the given node\n");
printf("7.Insert new node at the given node\n");
printf("8.Delete node\n");
printf("9.Reverse list\n");
printf("10.Quit\n\n");
printf("Enter your choice : ");
scanf("%d", &choice);
while(choice != 10){
switch(choice){
case 1:
display(head);
break;
case 2:
printf("List has %d elements.\n", count(head));
break;
case 3:
printf("Enter the data to find : ");
scanf("%d", &data);
search(head, data);
break;
case 4:
printf("Enter the data to insert at beginning : ");
scanf("%d", &data);
head = insert_at_beg(head,data);
break;
case 5:
printf("Enter the data to insert at end : ");
scanf("%d", &data);
head = insert_at_end(head,data);
break;
case 6:
printf("Insert data after node : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
head = insert_after(head, pos, data);
break;
case 7:
printf("Insert data at node number : ");
scanf("%d", &pos);
printf("Enter the data to insert : ");
scanf("%d", &data);
head = insert_at_pos(head, pos, data);
break;
case 8:
printf("Enter the data to delete : ");
scanf("%d", &data);
head = del_node(head, data);
break;
case 9:
printf("Reversing Single Linked List is time taking. \n");
break;
case 10:
break;
default:
printf("Enter choice less than 10. \n");
}
display(head);
printf("Enter your choice : ");
scanf("%d", &choice);
}
return 0;
}
```
### Drawbacks
- More memory space needed, 2 pointers.
- Need to manage more number of pointer operations when perform any operation.
## Circular Linked list
- After end, circle back to start.
- circular SLL & DLL
- Edge cases:
- add/remove start or end node then adjust the alternate linked node.
- Traversing : no NULL pointer, so p==head again after full traversal.
## Stack
- LIFO : Last In First Out , Last one put in will come out first.
- every object lies above or below some object.
- Eg : stack of books, stack of plates.
- stack can be implemented using arrays or linked-list.
- maintain a pointer top to keep track of top element.
### Usecases
- Expression Evaluation , Eg `x = 23 + 2 * 6 / 4 - 2` (based on precedence).
- Parenthesis check .
- Recursion call-stack.
- Many more advanced applications in computer science.
### Infix to postfix
```c
#include<stdio.h>
#include<ctype.h>
char Stack[20]; //Global stack
int top = -1;
void push(char x){
Stack[++top] = x;
}
char pop(){
if(top < 0)
return -1;
return Stack[top--];
}
int priority(char x){
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return -1;
}
char* infixToPostfix(char* exp, char* res){
int pos = 0;
char x;
while(*exp != '\0'){
if(isalnum(*exp)) //number
*(res + pos++) = *exp;
else if(*exp == '(') //parenthesis
push(*exp);
else if(*exp == ')')
{
while(top > -1 && (x = pop()) != '('){
*(res + pos++) = x;
}
}
else
{
while(top > -1 && (priority(Stack[top]) >= priority(*exp))){
*(res + pos++) = pop();
}
push(*exp);
}
exp++;
}
while( top > -1){
*(res + pos++) = pop();
}
*(res+pos) = '\0';
return res;
};
int main(){
char exp[20] = "(2*3+4*(5-6))";
char res[20];
printf("Infix : %s .\n", exp);
printf("Postfix : %s .\n", infixToPostfix(exp,res));
return 0;
}
```
### Infix to prefix
- Method 1:
- Reverse the intital expression string by replacing '(' with ')' and ')' with '('.
- apply postfix conversion on reversed expression string.
- reverse the obtained postfix expression to get prefix string.
### Evaluation of postfix expressions.
1. read each char of string one by one.
2. If char is an operand, push it to the stack.
3. If char is an operator, pop and store two elements from char, apply the operator on popped element, push the result onto the stack.
4. Pop result at last.
```c
#include<stdio.h>
#include<ctype.h>
char Stack[20]; //Global stack
int top = -1;
int StackI[20];
int topI = -1;
void push(char x){
Stack[++top] = x;
}
char pop(){
if(top < 0)
return -1;
return Stack[top--];
}
void pushI(int x){
StackI[++topI] = x;
}
char popI(){
if(topI < 0)
return -1;
return StackI[topI--];
}
int priority(char x){
if(x == '(')
return 0;
if(x == '+' || x == '-')
return 1;
if(x == '*' || x == '/')
return 2;
return -1;
}
int charToDigit(char x){
switch (x)
{
case '0':
return 0;
case '1':
return 1;
case '2':
return 2;
case '3':
return 3;
case '4':
return 4;
case '5':
return 5;
case '6':
return 6;
case '7':
return 7;
case '8':
return 8;
case '9':
return 9;
default:
printf("Something went wrong.\n");
}
return -1;
}
int postfixEvaluation(char* exp){
topI = -1;
while(*exp != '\0'){
printf("***Iteration***\n");
printf("Expr : %s \n", exp);
if(isalnum(*exp)){
pushI(charToDigit(*exp));
printf("digit : %d\n", charToDigit(*exp));
}else{
if(topI<1){
printf("Not Enough operands to use operator %c.\n",*exp);
return 0;
}
int a = popI();
int b = popI();
switch (*exp)
{
case '+':
pushI(b+a);
break;
case '-':
pushI(b-a);
break;
case '*':
pushI(b*a);
break;
case '/':
pushI(b/a);
break;
default:
printf("%c not valid operator.\n",*exp);
return 0;
}
}
exp++;
}
if(topI!=0){
printf("Invalid Postfix expression.\n");
return 0;
}
return popI();
}
char* infixToPostfix(char* exp, char* res){
int pos = 0;
char x;
while(*exp != '\0'){
if(isalnum(*exp)) //number
*(res + pos++) = *exp;
else if(*exp == '(') //parenthesis
push(*exp);
else if(*exp == ')')
{
while(top > -1 && (x = pop()) != '('){
*(res + pos++) = x;
}
}
else
{
while(top > -1 && (priority(Stack[top]) >= priority(*exp))){
*(res + pos++) = pop();
}
push(*exp);
}
exp++;
}
while( top > -1){
*(res + pos++) = pop();
}
*(res+pos) = '\0';
return res;
};
int main(){
char exp[20] = "(2*3+4*(5-6))";
char res[20];
printf("Infix : %s .\n", exp);
printf("Postfix : %s .\n", infixToPostfix(exp,res));
printf("Evaluation of postix expression : %d", postfixEvaluation( infixToPostfix(exp,res) ));
return 0;
}
```
### Operations on a stack
- push : add a new element on top of the stack, and top points to it.
- pop : removes and return the top element form the stack.
-
Leave a Comment