a) Does this 'Newsort' correctly sort the array? Why? b) find a recurrence for Newsort(T(n) = ?)
a) Does this 'Newsort' correctly sort the array? Why? b) find a recurrence for Newsort(T(n) = ?)
Database System Concepts
7th Edition
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Chapter1: Introduction
Section: Chapter Questions
Problem 1PE
Related questions
Question
python
![### Newsort Function
**Function Definition:**
```plaintext
given function 'newsort', consider a and b
newsort (array, a, b):
if array[a] > array[b]
Exchange array[a] <-> array[b]
if (a + 1) >= b
return
k <- int((b-a+1)/3) # the "int" function acts as floor
newsort (array, a, b-k)
newsort (array, a+k, b)
newsort (array, a, b-k)
```
**Explanation:**
1. **Exchange Logic:**
- If the element at index `a` is greater than the element at index `b`, the two elements are swapped.
2. **Base Case:**
- If `a + 1` is greater than or equal to `b`, the function returns, meaning the section of the array is either sorted or trivially short (1 or 0 elements).
3. **Recursive Steps:**
- The interval `[a, b]` is divided into sections to be recursively sorted:
- First section: indices from `a` to `b-k`.
- Second section: indices from `a+k` to `b`.
- Third section: again the first section for reinforcement.
4. **Partitioning:**
- The interval size `k` is calculated as the integer part of `(b-a+1)/3`, effectively dividing the range into thirds.
### Questions
**a) Does this 'Newsort' correctly sort the array? Why?**
- **Explanation:**
The recursive nature of the `newsort` function attempts to sort segments of the array by continuously narrowing the range to smaller sections. However, the efficacy of the algorithm above in fully sorting an input array isn’t straightforward. Because the recursive calls do not effectively ensure the entire array is considered consistently in a way that typical divide-and-conquer sorting algorithms (like quicksort or mergesort) do, it’s unlikely to correctly sort the array in all cases.
**b) Find a recurrence for Newsort \(T(n) = ?\)**
- **Recurrence Relation:**
The recurrence relation for `newsort` attempting to divide the array into thirds can be expressed as:
\[
T(n) = 3T\left(\frac{2n}{3}\right)](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2F12c18db6-f6e8-4129-b933-2f1b3972f7de%2F68f87482-acb2-480e-ae6e-a255e229e1b2%2Fjgguzkv_processed.png&w=3840&q=75)
Transcribed Image Text:### Newsort Function
**Function Definition:**
```plaintext
given function 'newsort', consider a and b
newsort (array, a, b):
if array[a] > array[b]
Exchange array[a] <-> array[b]
if (a + 1) >= b
return
k <- int((b-a+1)/3) # the "int" function acts as floor
newsort (array, a, b-k)
newsort (array, a+k, b)
newsort (array, a, b-k)
```
**Explanation:**
1. **Exchange Logic:**
- If the element at index `a` is greater than the element at index `b`, the two elements are swapped.
2. **Base Case:**
- If `a + 1` is greater than or equal to `b`, the function returns, meaning the section of the array is either sorted or trivially short (1 or 0 elements).
3. **Recursive Steps:**
- The interval `[a, b]` is divided into sections to be recursively sorted:
- First section: indices from `a` to `b-k`.
- Second section: indices from `a+k` to `b`.
- Third section: again the first section for reinforcement.
4. **Partitioning:**
- The interval size `k` is calculated as the integer part of `(b-a+1)/3`, effectively dividing the range into thirds.
### Questions
**a) Does this 'Newsort' correctly sort the array? Why?**
- **Explanation:**
The recursive nature of the `newsort` function attempts to sort segments of the array by continuously narrowing the range to smaller sections. However, the efficacy of the algorithm above in fully sorting an input array isn’t straightforward. Because the recursive calls do not effectively ensure the entire array is considered consistently in a way that typical divide-and-conquer sorting algorithms (like quicksort or mergesort) do, it’s unlikely to correctly sort the array in all cases.
**b) Find a recurrence for Newsort \(T(n) = ?\)**
- **Recurrence Relation:**
The recurrence relation for `newsort` attempting to divide the array into thirds can be expressed as:
\[
T(n) = 3T\left(\frac{2n}{3}\right)
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Recommended textbooks for you
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
Database System Concepts
Computer Science
ISBN:
9780078022159
Author:
Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:
McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:
9780134444321
Author:
Tony Gaddis
Publisher:
PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:
9780132737968
Author:
Thomas L. Floyd
Publisher:
PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:
9780133976892
Author:
Paul J. Deitel, Harvey Deitel
Publisher:
PEARSON
Database Systems: Design, Implementation, & Manag…
Computer Science
ISBN:
9781337627900
Author:
Carlos Coronel, Steven Morris
Publisher:
Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:
9780073373843
Author:
Frank D. Petruzella
Publisher:
McGraw-Hill Education