Untitled
unknown
plain_text
5 months ago
27 kB
1
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. Last node points to the first node again.
- USecases : playlists, OS uses CLL for running programs.
- 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.
> Implement the CLL code yourself.
## Questions
```
1. In Insertionsort even if we use binary search to find the correct place of an element, still we have to move all elemnets to the right, so it will take O(n^2).
```
## Stack
- LIFO : Last In First Out , Last one putin 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.
- top is a pointer pointing to the top element of stack.
### 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.
### 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.
### Stack using arrays
- stores elements in contigious memory loacation.
- Sequential access available nut not need because of top pointer.
- disadvantage that once we push elements equal to maximum capacity of array, we can't push further.
### Infix to postfix
```c
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
char stack[20];
int top = -1;
void push(char ch){
stack[++top] = ch;
}
char pop(){
if(top < 0)
return ' ';
return stack[top--];
}
int priority(char ch){
if(ch == '(')
return 0;
else if(ch == '+' || ch == '-')
return 1;
else if(ch == '*' || ch == '/')
return 2;
return -1;
}
char* infix_to_postfix(char str[20]){
char* res = (char*) calloc(20, sizeof(char));
char *exp = str, temp;
int i=0;
while(*exp != '\0'){
if(isalnum(*exp))
res[i++] = *exp;
else if(*exp == '(')
push(*exp);
else if(*exp == ')'){
while((temp = pop()) != '('){
res[i++] = temp;
}
} else {
while(top > -1 && priority(stack[top]) >= priority(*exp)){
res[i++] = pop();
}
push(*exp);
}
exp++;
}
return res;
}
int main(){
char str[20] = "(2*3+4*(5-6))";
printf("%s\n", infix_to_postfix(str));
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<stdlib.h>
#include<ctype.h>
char stack[20];
int top = -1;
void push(char ch){
stack[++top] = ch;
}
char pop(){
if(top < 0)
return ' ';
return stack[top--];
}
int priority(char ch){
if(ch == '(')
return 0;
else if(ch == '+' || ch == '-')
return 1;
else if(ch == '*' || ch == '/')
return 2;
else
return -1;
}
char* infix_to_postfix(char str[20]){
char* res = (char*) calloc(20, sizeof(char));
char *exp = str, temp;
int i=0;
while(*exp != '\0'){
if(isalnum(*exp))
res[i++] = *exp;
else if(*exp == '(')
push(*exp);
else if(*exp == ')'){
while((temp = pop()) != '('){
res[i++] = temp;
}
} else {
while(top > -1 && priority(stack[top]) >= priority(*exp)){
res[i++] = pop();
}
push(*exp);
}
exp++;
}
res[i] = '\0';
return res;
}
int int_Stack[20];
int int_top = -1;
int getdigit(char ch){
switch(ch){
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("Not valid digit.\n");
}
return -1;
}
// only for for expression having single digit operands.
int postfix_evaluation(char* postfix){
char* ptr = postfix;
while(*ptr != '\0'){
if(isalnum(*ptr)){
int_Stack[++int_top] = getdigit(*ptr);
}else{
if(int_top > 0){
int b = int_Stack[int_top--];
int a = int_Stack[int_top--];
switch(*ptr){
case '+' : int_Stack[++int_top] = a+b;
break;
case '-' : int_Stack[++int_top] = a-b;
break;
case '*' : int_Stack[++int_top] = a*b;
break;
case '/' : int_Stack[++int_top] = a/b;
break;
default :
printf("Not a valid operator.\n");
}
}
}
ptr++;
}
if(int_top == 0)
return int_Stack[int_top--];
printf("Not a valid postfix expression. \n");
return 0;
}
int main(){
char infix[20] = "(2*3+4*(5-6))";
char* postfix = infix_to_postfix(infix);
printf("Infix : %s\n", infix);
printf("Postfix : %s\n", postfix);
printf("Postfix Evaluation : %d. \n", postfix_evaluation(postfix));
return 0;
}
```
### Evaluation of prefix expressions
- similar to postfix, just traverse the expression in reverse order.
### Call-Stack
- It is also known as runtime-stack or machine-stack, and is useful for maintaining function call sequence.
- It is very useful for recursion.
- Call stack contains frame's . Each frame has several fields, which has information about calling function.
```
[fact(1) 1 ] }frame
[fact(2) 2*fact(1)] }frame [fact(2) 2*1 ]
[fact(3) 3*fact(2)] }frame -> [fact(3) 3*fact(2)] -> [fact(3) 3*2 ] -> -> ->120.
[fact(4) 4*fact(3)] }frame [fact(4) 4*fact(3)] [fact(4) 4*fact(3)] [fact(4) 4*6 ]
[fact(5) 5*fact(4)] }frame [fact(5) 5*fact(4)] [fact(5) 5*fact(4)] [fact(5) 5*fact(4)] [fact(5) 5*24]
```
- keep track of which function called another function.
- Space complexity : O(n) // due to call stack.
- quicksort in worst case takes theta(n) space for call stack.
### sedwgick modified quicksort algorithm.
- objective : reduce worst case space complexity of quicksort from theta(n) to theta(log(n)).
```
quicksort(A, p, r):
while (p < r) // both iterative and recursive.
q = PARTITION(A, p, r);
// Recurse the smaller subarray first.
if(q - p < r - q)
quicksort(A, p, q - 1)
p = q + 1
else
quicksort(A, q + 1, r)
r = q - 1
```
- How this works :
1. reursively quicksort the smaller subarray.
2. return back to calling function, and updates the variables.
3. recursively quicksort the larger subarray.
> Left associative means perform operation from left to right. Right associative means perform operation from right to left.
> Due to slow random access of doubly linked list, only meregesort O(nLogn) or insertion sort O(n^2) can be used optimally on doubly linkws liar.
## Print linkedlist in reverse order.
```c
void reversePrintLL(node *head){
if(head == NULL){
return;
}
reversePrintLL(head->next);
printf("%d ",head->data);
}
```
## Queues
- queues are FIFO data structures.
- First item to come in is the first to be served(out).
- Operations :
- Enqueue : Add to the queue. (Always add to the tail)
- Dequeue : Remove from the queue. (Always remove from the head)
> In Stack one pointer(top) was sufficient, in Queue we need 2 Pointers (head and tail).
### Implementation using a linkedlist.
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node{
int data;
struct Node *next;
}node;
typedef struct{
node *head;
node *tail;
}queue;
queue *enque(queue *qlist, int info){
node *temp = (node*) malloc(sizeof(node));
temp->data = info;
temp->next = NULL;
if(qlist->tail == NULL){
qlist->head = temp;
qlist->tail = temp;
}
qlist->tail->next = temp;
qlist->tail = temp;
return qlist;
}
queue *deque(queue *qlist){
if(qlist->head == NULL){
printf("List is Empty. \n");
return qlist;
}
node *temp = qlist->head;
qlist->head = qlist->head->next;
if(qlist->head->next == NULL)
qlist->tail = NULL;
int info = temp->data;
free(temp);
return info;
}
int main(){
node node2 = {20, NULL};
node node1 = {10, &node1};
queue q, *qlist;
qlist = &q;
qlist->head = &node1;
qlist->tail = &node2;
return 0;
}
```
Leave a Comment